Giả sử chúng ta có một lưới, có vài số 0 và vài số 1. Chúng ta phải đếm số lượng các hòn đảo. Đảo là nơi được bao quanh bởi nước và được hình thành bằng cách kết nối các vùng đất liền kề theo chiều ngang hoặc chiều dọc. Chúng ta có thể giả định rằng tất cả bốn cạnh của lưới đều được bao quanh bởi nước.
Giả sử lưới giống như -
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 |
Có ba hòn đảo.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Sẽ có hai phương thức, một phương thức sẽ được sử dụng để đếm số hòn đảo được gọi là numIslands () và makeWater (). MakeWater () sẽ giống như -
- nếu số hàng trong lưới là 0, thì trả về 0
- n =số hàng và m:=số cột và ans:=0
- cho tôi trong phạm vi từ 0 đến n - 1
- cho j trong phạm vi từ 0 đến m
- nếu lưới [i, j] =1, thì ans:=ans + 1
- makeWater (i, j, n, m, lưới)
- cho j trong phạm vi từ 0 đến m
- the makeWater () sẽ lấy các chỉ số i, j, hàng và col đếm n và m và lưới
- nếu tôi <0 hoặc j <0 hoặc i> =n hoặc j> =m, thì trả về từ phương thức này
- nếu grid [i, j] =0, thì trả về nếu không, hãy tạo lưới [i, j]:=0
- gọi makeWater (i + 1, j, n, m, lưới)
- gọi makeWater (i, j + 1, n, m, lưới)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution(object): def numIslands(self, grid): if len(grid) == 0: return 0 n= len(grid) m = len(grid[0]) ans = 0 for i in range(n): for j in range(m): if grid[i][j] == "1": ans+=1 self.make_water(i,j,n,m,grid) return ans def make_water(self,i,j,n,m,grid): if i<0 or j<0 or i>=n or j>=m: return if grid[i][j] == "0": return else: grid[i][j]="0" self.make_water(i+1,j,n,m,grid) self.make_water(i,j+1,n,m,grid) self.make_water(i-1,j,n,m,grid) self.make_water(i,j-1,n,m,grid) ob1 = Solution() print(ob1.numIslands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"], ["0","0","0","1","1"]]))
Đầu vào
[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Đầu ra
3