## 题目描述：

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

```11110
11010
11000
00000```

Example 2:

```11000
11000
00100
00011```

## 解题思路：

FloodFill，BFS（广度优先搜索）或者DFS（深度优先搜索）均可。

Python代码：

``````class Solution:
# @param grid, a list of list of characters
# @return an integer
def numIslands(self, grid):
ans = 0
if not len(grid):
return ans
m, n = len(grid), len(grid)
visited = [ [False] * n for x in range(m) ] # m * n
for x in range(m):
for y in range(n):
if grid[x][y] == '1' and not visited[x][y]:
ans += 1
self.bfs(grid, visited, x, y, m, n)
return ans

def bfs(self, grid, visited, x, y, m, n):
dz = zip( [1, 0, -1, 0], [0, 1, 0, -1] )
queue = [ (x, y) ]
visited[x][y] = True
while queue:
front = queue.pop(0)
for p in dz:
np = (front + p, front + p)
if self.isValid(np, m, n) and grid[np][np] == '1' and not visited[np][np]:
visited[ np ][ np ] = True
queue.append(np)

def isValid(self, np, m, n):
return np >= 0 and np < m and np >= 0 and np < n
`````` Pingbacks已关闭。

1. joshua 发布于 2018年8月28日 12:20 #

我觉得楼主答案没什么问题,不过copy结果是这样,很纳闷
Input:
[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
Output:
5
Expected:
1