掌握 floodfill 算法，更加深入体会深度优先遍历的应用。这个算法其实非常简单，属于基础的算法。解决的思路是非常标准的。floodfill 的本质其实是深度优先遍历。
例1：LeetCode 第 200 题：岛屿的个数
给定一个由
'1'（陆地）和'0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。示例 1:
输入: 11110 11010 11000 00000 输出: 1示例 2:
输入: 11000 11000 00100 00011 输出: 3
要求：给定一个二维数组，只含有 0 和 1 两个字符。其中 1 代表陆地，0 代表水域。横向和纵向的陆地连接成岛屿，被水域分隔开。问给出的地图中有多少岛屿？
分析：
- 四个方向的顺序其实无所谓；
- 递归终止条件已经包含在 if 中；
- 何处体现了回溯的过程？这里为什么不须要把状态还原和重置。
代码实现
Python 代码：
class Solution(object):
directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
marked = [[False for _ in range(n)] for _ in range(m)]
count = 0
for i in range(m):
for j in range(n):
if not marked[i][j] and grid[i][j] == '1':
self.dfs(grid, i, j, m, n, marked)
count += 1
return count
def dfs(self, grid, i, j, m, n, marked):
marked[i][j] = True
for direction in self.directions:
new_i = i + direction[0]
new_j = j + direction[1]
if 0 <= new_i < m and 0 <= new_j < n and not marked[
new_i][new_j] and grid[new_i][new_j] == '1':
self.dfs(grid, new_i, new_j, m, n, marked)
Java 代码：
public class Solution {
/*
* 这里可以复习一下二维数组的表示
*/
private int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1},};
private boolean[][] visited;
private int m;
private int n;
public int numIslands(char[][] grid) {
this.m = grid.length;
if (m == 0) {
return 0;
}
this.n = grid[0].length;
visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
visited[i][j] = false;
}
}
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 如果是岛屿中的一个点，并且没有被访问过
// 就进行深度优先遍历
if (grid[i][j] == '1' && !visited[i][j]) {
res++;
dfs(grid, i, j);
}
}
}
return res;
}
/**
* 从坐标为(i,j)的点开始进行深度优先遍历
*
* @param grid
* @param i
* @param j
*/
private void dfs(char[][] grid, int i, int j) {
visited[i][j] = true;
// 从 4 个方向走
for (int k = 0; k < 4; k++) {
int newX = i + d[k][0];
int newY = j + d[k][1];
// 如果不越界，如果还没有被访问过
if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == '1') {
dfs(grid, newX, newY);
}
}
}
private boolean inArea(int newX, int newY) {
// 等于号这些细节不要忘了
return newX >= 0 && newX < m && newY >= 0 && newY < n;
}
public static void main(String[] args) {
Solution solution = new Solution();
char[][] grid1 = {
{'1', '1', '1', '1', '0'},
{'1', '1', '0', '1', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '0', '0', '0'}};
int numIslands1 = solution.numIslands(grid1);
System.out.println(numIslands1);
char[][] grid2 = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}};
int numIslands2 = solution.numIslands(grid2);
System.out.println(numIslands2);
}
}
要注意的问题：
1、char 和 int 不一样，测试用例不要写成 int 数组了；
2、floodfill 算法的实现其实就是一次深度优先遍历；
3、递归终止条件隐含在判断中了；
4、没有把状态置回的过程，看起来不像回溯，但是没有必要纠结这个；
5、调试的过程中，要有耐心，把每一步的变量都打印出来，会比 debug 效率更高；
6、数组的下标可以自己画一个表格出来，就很清晰了。
练习
练习1：LeetCode 第 130 题：被围绕的区域
传送门：130. 被围绕的区域。
给定一个二维的矩阵，包含
'X'和'O'（字母 O）。找到所有被
'X'围绕的区域，并将这些区域里所有的'O'用'X'填充。示例:
X X X X X O O X X X O X X O X X运行你的函数后，矩阵变为：
X X X X X X X X X X X X X O X X解释:
被围绕的区间不会存在于边界上，换句话说，任何边界上的
'O'都不会被填充为'X'。 任何不在边界上，或不与边界上的'O'相连的'O'最终都会被填充为'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
分析：因为不涉及到最少步或者最优解问题。 这道题可以有很多解法 BFS、DFS、UNION FIND。
思路：不要想着怎么把连通区域找到，反而是想怎么把连通边界找到。
首先对边界上每一个 'O' 做深度优先搜索，将与其相连的所有 'O' 改为 '-' 。然后遍历矩阵，将矩阵中所有 'O' 改为 'X' ，将矩阵中所有 '-' 变为 'O'。
于是问题就转换成了如何将边界上与最开始的 'O' 改为 '-' 这个问题。
Python 实现：
class Solution:
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
global m, n, directions
m = len(board)
if m == 0:
return
n = len(board[0])
directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
for row_index in range(m):
self.__flood_fill(board, row_index, 0)
self.__flood_fill(board, row_index, n - 1)
for col_index in range(1, n - 1):
self.__flood_fill(board, 0, col_index)
self.__flood_fill(board, m - 1, col_index)
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
if board[i][j] == '-':
board[i][j] = 'O'
def __flood_fill(self, board, x, y):
if 0 <= x < m and 0 <= y < n and board[x][y] == 'O':
board[x][y] = '-'
for direction in directions:
new_x = x + direction[0]
new_y = y + direction[1]
self.__flood_fill(board, new_x, new_y)
说明：可以发现，这里我们没有设置 marked 数组，这是因为，我们把 'O' 修改成 '-' 这个操作，就相当于 markded 了。
参考资料：https://blog.csdn.net/qq_17550379/article/details/82688731
解法2：广度优先遍历
Python 代码：
# 130. 被围绕的区域
# 给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
# 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
# https://segmentfault.com/a/1190000012898131
class Solution:
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
global m, n, directions
m = len(board)
if m == 0:
return
n = len(board[0])
directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
for row_index in range(m):
self.__flood_fill(board, row_index, 0)
self.__flood_fill(board, row_index, n - 1)
for col_index in range(1, n - 1):
self.__flood_fill(board, 0, col_index)
self.__flood_fill(board, m - 1, col_index)
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
if board[i][j] == '-':
board[i][j] = 'O'
def __flood_fill(self, board, x, y):
# 不管怎么样，根结点先入队
queue = [(x, y)]
while queue:
cur_x, cur_y = queue.pop(0)
# 出队的时候检查：1、坐标合法；2、是 "O"
# board[cur_x][cur_y] = '-' 就表示 marked 了，所以不用引入 marked 数组
# 两条都符合，就继续扩散开去
if 0 <= cur_x < m and 0 <= cur_y < n and board[cur_x][cur_y] == 'O':
board[cur_x][cur_y] = '-'
for direction in directions:
new_x = cur_x + direction[0]
new_y = cur_y + direction[1]
queue.append((new_x, new_y))
if __name__ == '__main__':
# board = [['X', 'X', 'X', 'X'],
# ['X', 'O', 'O', 'X'],
# ['X', 'X', 'O', 'X'],
# ['X', 'O', 'X', 'X']]
# board = [['O', 'O', 'O'],
# ['O', 'O', 'O'],
# ['O', 'O', 'O']]
# board = [["X", "O", "X", "O", "X", "O"],
# ["O", "X", "O", "X", "O", "X"],
# ["X", "O", "X", "O", "X", "O"],
# ["O", "X", "O", "X", "O", "X"]]
# 极端测试用例
board = [["X", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O"],
["O", "X", "O", "O", "O", "O", "X", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "X", "X"],
["O", "O", "O", "O", "O", "O", "O", "O", "X", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "X"],
["O", "O", "X", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "X", "O"],
["O", "O", "O", "O", "O", "X", "O", "O", "O", "O", "X", "O", "O", "O", "O", "O", "X", "O", "O", "X"],
["X", "O", "O", "O", "X", "O", "O", "O", "O", "O", "X", "O", "X", "O", "X", "O", "X", "O", "X", "O"],
["O", "O", "O", "O", "X", "O", "O", "X", "O", "O", "O", "O", "O", "X", "O", "O", "X", "O", "O", "O"],
["X", "O", "O", "O", "X", "X", "X", "O", "X", "O", "O", "O", "O", "X", "X", "O", "X", "O", "O", "O"],
["O", "O", "O", "O", "O", "X", "X", "X", "X", "O", "O", "O", "O", "X", "O", "O", "X", "O", "O", "O"],
["X", "O", "O", "O", "O", "X", "O", "O", "O", "O", "O", "O", "X", "X", "O", "O", "X", "O", "O", "X"],
["O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "X", "O", "O", "X", "O", "O", "O", "X", "O", "X"],
["O", "O", "O", "O", "X", "O", "X", "O", "O", "X", "X", "O", "O", "O", "O", "O", "X", "O", "O", "O"],
["X", "X", "O", "O", "O", "O", "O", "X", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O"],
["O", "X", "O", "X", "O", "O", "O", "X", "O", "X", "O", "O", "O", "X", "O", "X", "O", "X", "O", "O"],
["O", "O", "X", "O", "O", "O", "O", "O", "O", "O", "X", "O", "O", "O", "O", "O", "X", "O", "X", "O"],
["X", "X", "O", "O", "O", "O", "O", "O", "O", "O", "X", "O", "X", "X", "O", "O", "O", "X", "O", "O"],
["O", "O", "X", "O", "O", "O", "O", "O", "O", "O", "X", "O", "O", "X", "O", "X", "O", "X", "O", "O"],
["O", "O", "O", "X", "O", "O", "O", "O", "O", "X", "X", "X", "O", "O", "X", "O", "O", "O", "X", "O"],
["O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O", "O"],
["X", "O", "O", "O", "O", "X", "O", "O", "O", "X", "X", "O", "O", "X", "O", "X", "O", "X", "O", "O"]]
# 执行用时: 140 ms, 在Surrounded Regions的Python3提交中击败了92.24% 的用户
solution = Solution()
solution.solve(board)
for row in board:
print(row)
练习2：LeetCode 第 417 题：太平洋大西洋水流问题
传送门：417. 太平洋大西洋水流问题。
给定一个
m x n的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
提示：
- 输出坐标的顺序不重要
- m 和 n 都小于150
示例：
给定下面的 5x5 矩阵: 太平洋 ~ ~ ~ ~ ~ ~ 1 2 2 3 (5) * ~ 3 2 3 (4) (4) * ~ 2 4 (5) 3 1 * ~ (6) (7) 1 4 5 * ~ (5) 1 1 2 4 * * * * * * 大西洋 返回: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
（本节完）
