Giả sử chúng ta có một lưới 2D, chứa các màu là các chuỗi "r", "g" và "b". Chúng ta phải thực hiện thao tác lấp đầy tại hàng r, cột c với mục tiêu màu. Như chúng ta đã biết, hoạt động Floodfill sẽ thay thế tất cả các phần tử được kết nối với lưới [r, c] (lên / phải / xuống / trái) và có cùng màu với lưới [r, c] bằng cùng màu với mục tiêu.
Vì vậy, nếu đầu vào giống như
| R | R | R |
| R | G | B |
| G | B | B |
thì đầu ra sẽ là
| G | G | G |
| G | G | B |
| G | B | B |
vì các ô màu đỏ kết nối với lưới [0,0] được thay thế bằng màu xanh lục ("g").
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- xác định một tập hợp mới được xem
- oldcolor:=matrix [r, c]
- Định nghĩa một hàm dfs (). Điều này sẽ mất tôi, j
- nếu i và j nằm trong ma trận và (i, j) không được nhìn thấy và ma trận [i, j] giống với oldcolor, thì
- thêm (i, j) trong số đã xem
- ma trận [i, j]:=target
- dfs (i + 1, j)
- dfs (i, j + 1)
- dfs (i, j - 1)
- dfs (i - 1, j
- Từ phương pháp chính, hãy thực hiện như sau -
- dfs (r, c)
- ma trận trả về
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution: def solve(self, matrix, r, c, target): def dfs(i, j): if ( i >= 0 and i < len(matrix) and j >= 0 and j < len(matrix[0]) and (i, j) not in seen and matrix[i][j] == oldcolor ): seen.add((i, j)) matrix[i][j] = target dfs(i + 1, j) dfs(i, j + 1) dfs(i, j - 1) dfs(i - 1, j) seen = set() oldcolor = matrix[r][c] dfs(r, c) return matrix ob = Solution() matrix = [ ["r", "r", "r"], ["r", "g", "b"], ["g", "b", "b"] ] r = 0 c = 0 target = "g" print(ob.solve(matrix, r, c, target))
Đầu vào
matrix = [ ["r", "r", "r"], ["r", "g", "b"], ["g", "b", "b"] ] r = 0 c = 0 target = "g"
Đầu ra
[ ['g', 'g', 'g'], ['g', 'g', 'b'], ['g', 'b', 'b']]