LeetCode#200. Number of Islands

发表于 | 分类于 ， ，

LeetCode#200 Number of Islands

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:

1
2
3
4
11110
11010
11000
00000

Answer: 1

Example 2:

1
2
3
4
11000
11000
00100
00011

Answer: 3

分析

这道题比较简单，很容易就能想到遍历到grid(x, y) = 1的上下左右各数，如果为1则与grid(x, y)在同一个“岛屿”。深度优先搜索正好可以应用在这种场景下。每当完成一次搜索，就找到了一个岛屿。为了避免重复搜索，可以每搜索到一块陆地就将其设置为已搜索。如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void dfs(x, y, grid)     // grid是地图，其类型是char[][], x是地图的行，y是地图的列
  if (grid[x][y] = '1')  // 如果找到一块没有被访问过的陆地，则将其标记为已访问，并开始深搜
    grid[x][y] = 'x'
  else
    return // 如果不是陆地或者已经访问过，则结束

  // 访问上下左右各个节点
  if (x > 0)
    dfs(x - 1, y, grid)

  if (x < grid.length - 1)
    dfs(x + 1, y, grid)

  if (y > 0)
    dfs(x, y - 1, grid)

  if (y < grid[x].length - 1)
    dfs(x, y + 1, grid)

int numIslands(grid)      // grid是地图，其类型是char[][]
  count = 0
  for (i = 0; i < grid.length; i++)
    gridRow = grid[i]
    for (j = 0; j < gridRow.length; j++)
      // 如果节点已经被访问过或者不是陆地，则跳过
      if (gridRow[j] = 'x' || gridRow[j] = '0')
        continue

      // 岛的数量加一
      count++
      // 开始遍历与此陆地同一个岛的所有陆地
      dfs(i, j, grid)

  return count