LeetCode 解题报告 (200,130)-- 图的孤立子图

发表于 标签 ， ， ，

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:

11110 11010 11000 00000

Answer: 1

上面的问题是一个经典的图论问题，需要求孤立的岛屿的个数，而岛屿仅可通过上下左右来连接，这种问题可以通过深度优先搜索 (DFS) 或广度优先搜索 (BFS) 来解决，每次遇到一个没访问过的岛屿就对当前岛屿进行 DFS 或 DFS，并记录这个过程中访问过的岛屿，直至最终所有岛屿都被访问

采用 DFS 的的 python 代码如下所示：

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
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if len(grid) == 0: return 0
        m, n, result = len(grid), len(grid[0]), 0
        visited = [[0 for j in xrange(n)] for i in xrange(m)]
        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j] == '1' and visited[i][j] == 0:
                    self.dfs(grid, visited, i, j)
                    result += 1
        return result

    def dfs(self, grid, visited, i, j):
        visited[i][j] = 1
        m, n = len(grid), len(grid[0])
        if 0<= i-1 <m and grid[i-1][j] == '1' and visited[i-1][j] == 0:
            self.dfs(grid, visited, i-1, j)
        if 0<= i+1 <m and grid[i+1][j] == '1' and visited[i+1][j] == 0:
            self.dfs(grid, visited, i+1, j)
        if 0<= j-1 <n and grid[i][j-1] == '1' and visited[i][j-1] == 0:
            self.dfs(grid, visited, i, j-1)
        if 0<= j+1 <n and grid[i][j+1] == '1' and visited[i][j+1] == 0:
            self.dfs(grid, visited, i, j+1)

假如将上面的题目改为一个岛屿邻接的岛屿除了上下左右，还有左上、左下、右上、右下，也就是有八个可能连接的地方，那么答案该如何修改？

实际上方法也很简单，对上面代码中的 dfs 方法增加检查左上、左下、右上、右下这四个点的代码即可。

上面的 DFS 中利用了 visited 数组检查某个点是否已经被访问过，空间复杂度为 O(m*n)。实际上在原来的 grid 可修改的情况下，可以通过修改 grid 中的值为 '1','0' 以外的值，从而使得空间复杂度为 O (1)。下面的 BFS 方法利用了这点

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
35
36
37
from collections import deque
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        m = len(grid)
        if m == 0:
            return 0
        n = len(grid[0])
        count = 0
        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j] == '1':
                    self.bfs(i, j, grid)
                    count += 1
        return count
    def bfs(self, row, col, grid):
        m, n = len(grid), len(grid[0])
        que = deque()
        que.append((row, col))
        grid[row][col] = '2'
        while que:
            row, col = que.popleft()
            if row>0 and grid[row-1][col]=='1':
                que.append((row-1, col))
                grid[row-1][col] = '2'
            if row<m-1 and grid[row+1][col] == '1':
                que.append((row+1, col))
                grid[row+1][col] = '2'
            if col>0 and grid[row][col-1]=='1':
                que.append((row, col-1))
                grid[row][col-1] = '2'
            if col<n-1 and grid[row][col+1] == '1':
                que.append((row, col+1))
                grid[row][col+1] = '2'

此外，130. Surrounded Regions跟上面的题目也类似，只是需要对边上的点进行 BFS 或 DFS，具体代码见这里