Flood fill算法及其应用

文章目录

1. 1. 岛的数量
2. 2. 投降的区域
3. 3. 找出二叉树中每行的最大值

Flood fill 是什么？
算法里还有洪水？😄这里就不掉书袋了，直接搬wikipedia链接

Flood fill算法是从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典算法。因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。在GNU Go和扫雷中，Flood Fill算法被用来计算需要被清除的区域。

实际上Flood fill 在fill的方式上可选DFS和BFS，这也决定了染色或者扩散的方式。事实上在很多链接区域问题上都有不同的取舍。
老规矩 “Talk is cheap, show me the code.”
同样的， 下面的问题都会给出两种语言(Java, Python)的实现。

岛的数量

原题传送门

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

Example 2:

11000
11000
00100
00011
Answer: 3

这个问题是flood fill类问题的经典问题之一， 正好通过这道题我们来看一下“洪水”是怎样传播下去的。
言归正传，拿到问题的第一件事情是审题，寻找描述二意的点，比如说，grid是否可能为空？grid是否会退化成一维数组？以及这两种条件下返回什么？等等类似的问题。

接下来就是思考可能的解法，直觉算法就是，从“岛”（“O”）开始遍历，然后按照DFS或者BFS的遍历方式遍历相邻“岛”（“O”），并且将遍历过的岛标记为”x“，每完成一块的遍历，计数器加一。算法的自然语言描述就是这样，下面开始分析算法复杂度：
时间复杂度： 不管是DFS还是BFS都需要遍历整个数组，只是遍历方式不同而以，但是复杂度都是$O(m * n)$ (m,n 分别是数组的行数和列数)
空间复杂度：由于没有用到额外的空间（auxilary space）因此空间复杂度为$O(1)$

暂时没有其他的算法思路了，如果DFS和BFS属于两个算法，那么目前看来，这两个就是比较好的解法了，那我们就以DFS为例实现算法：
先是Java版本

public class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int numberOfLands = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                     _dfs(grid, i, j, m, n);
                    numberOfLands ++;
                }
            }
        }

        return numberOfLands;
    }

    private void _dfs(char[][] grid, int i, int j, int maxRow, int maxCol) {
        if (i >= 0 && i < maxRow && j >= 0 && j < maxCol && grid[i][j] == '1') {
            grid[i][j] = 'm';
            for (int k = 0; k < 4; k++) {
                _dfs(grid, i+dx[k], j+dy[k], maxRow, maxCol);
            }
        }
    }
}

类似的有Python版本：

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        """
        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.
        """
        if grid is None or len(grid) == 0:return 0

        m, n = len(grid), len(grid[0])
        result = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    self._dfs(grid, i, j, m, n)
                    result += 1
        return result

    def _dfs(self, grid, i, j, m, n):
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        if 0 <= i < m and 0 <= j < n and grid[i][j] == '1':
            grid[i][j] = '0'
            for k in range(4):
                self._dfs(grid, i + dx[k], j + dy[k], m, n)

这样就完成了么？好像哪里有些不对。对的，相信你也发现了，就是我们将外面传进来的数组给修改了，多数情况下，这是不好的行为，当然好不好取决于这个接口使用者的定义，如果后续还要用到这个参数，那么在内部修改原来的行为就不好了，如果是这种情况，怎么办？
其实有两种选择，一种对于原来问题的修改成本低，几乎不修改原来算法的主要逻辑；而另一种则相对前一种麻烦些。下面我们一一说明：

• 第一种方案的思想是，不是不让修改么？那么我修改后恢复现场不就行了？
  以python为例：

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        """
        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.
        """
        if grid is None or len(grid) == 0:return 0

        m, n = len(grid), len(grid[0])
        result = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    self._dfs(grid, i, j, m, n)
                    result += 1
        # recover the scene
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'm':
                    grid[i][j] = '1'

        return result

    def _dfs(self, grid, i, j, m, n):
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        if 0 <= i < m and 0 <= j < n and grid[i][j] == '1':
            grid[i][j] = 'm'
            for k in range(4):
                self._dfs(grid, i + dx[k], j + dy[k], m, n)

• 第二种想法就是使用额外的空间来记录岛是否访问过。这样的话会使用额外的空间，因此空间复杂度就变成了$O(m * n)$, 当然这也是有适用场景的，如果传入的参数被设计为禁止修改，即使是恢复现场也不行的时候，这个算法也是有效的。

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        """
        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.
        """
        if grid is None or len(grid) == 0:return 0

        m, n = len(grid), len(grid[0])
        visited, result = [[0 for _ in range(n)] for _ in range(m)], 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1' and visited[i][j] == 0:
                    self._dfs(grid, visited, i, j, m, n)
                    result += 1
        return result

    def _dfs(self, grid, visited, i, j, m, n):
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        if 0 <= i < m and 0 <= j < n and grid[i][j] == '1' and visited[i][j] == 0:
            visited[i][j] = 1
            for k in range(4):
                self._dfs(grid, visited, i + dx[k], j + dy[k], m, n)

仔细想想好像还有些问题，比如说：

• visited 的数组空间是不是太大了，好像很多空间都没有用到，是不是可以优化。
• 既然BFS和DFS一样，那么BFS是不是也可以实现一下呢？

投降的区域

原题传输门

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

有了上一题的基础，这道题是不是就不那么难了呢？
我们直奔主题，
第一步还是审题，参数为空，长度为零，等等。
这里题意清楚，没什么过多解释的。
第二步列出所有可能的解决方案。这里如果是直接找出投降区域似乎还是有些难度的，那么我们去看它的另一面，找出没有四周被包围的区域，那么剩下的没有被占领的区域不就是找到了么？然后将这部分“投降区域”全部标记为占领就可以了。下面来分析算法复杂度： 时间复杂度：由于需要DFS或者BFS那么就需要遍历二维数组因此复杂度为$O(m * n)$ 其次空间复杂度：由于矩阵是可以修改的，所以我们可以做到inplace的修改，空间复杂度为$O(1)$
第三步实现并优化代码。
老规矩Java先来：

import javafx.util.Pair;

public class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;

        int m = board.length;
        int n = board[0].length;
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        HashSet<Pair<Integer, Integer>> visited = new HashSet<Pair<Integer, Integer>>();
        // find the edge not surrounded elements.
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O') {
                    queue.offer(new Pair<Integer, Integer>(i, j));
                }
            }
        }


        while (!queue.isEmpty()) {
            Pair<Integer, Integer> position = queue.poll();
            int x = position.getKey();
            int y = position.getValue();
            if (x >= 0 && x < m  && y >= 0 && y < n &&
                board[x][y] == 'O' && !visited.contains(position)) {
                board[x][y] = 'm';
                visited.add(position);

                for (int k = 0; k < 4; k++) {
                    queue.offer(new Pair<Integer, Integer>(x + dx[k], y + dy[k]));
                }
            }
         }

         for (int i = 0; i < m; i++) {
             for (int j = 0; j < n; j++) {
                 if (board[i][j] == 'O') {
                     board[i][j] = 'X';
                 } else if (board[i][j] == 'm') {
                     board[i][j] = 'O';
                 }
             }
         }
    }
}

接着是Python：

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if len(board) == 0:
            return

        m, n = len(board), len(board[0])

        if m <= 2 or n <= 2:
            return

        queue = deque()
        visited = set()
        # queue.append([0, 0])
        for i in range(m):
            for j in range(n):
                if (i in [0, m - 1] or j in [0, n - 1]) and board[i][j] == 'O':
                    queue.append((i, j))

        while queue:
            position = queue.popleft()
            visited.add(position)
            # do something

            if 0 <= position[0] < m and 0 <= position[1] < n and board[position[0]][position[1]] == 'O':
                board[position[0]][position[1]] = 'm'
                for i in range(4):
                    p = (position[0] + dx[i], position[1] + dy[i])
                    queue.append(p)

        # loop the board and mark the none-surrounded area, and mark back 'm' area
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'm':
                    board[i][j] = 'O'

这是使用BFS遍历方式的解法，DFS呢？可以实现么？
上面的问题都是Flood fill的典型问题，下面来点简单的。

找出二叉树中每行的最大值

原题传送门

You need to find the largest value in each row of a binary tree.

Example:
Input:

      1
     / \
    3   2
   / \   \  
  5   3   9

Output: [1, 3, 9]

解题第一步，先审题，判空，等等有二意的部分。本题比较温暖纯良，没有什么大坑。所以可以选择性略过。
第二步列出所有可能的解决方案：
直觉算法是BFS遍历整个二叉树，然后在遍历每层的过程中找出最大的值。这里的算法复杂度： 时间复杂度$O(n)$, 空间复杂度$O(1)$
DFS遍历可以么？应该也可以，只是需要遍历的同时记录遍历到那一层，时间和空间的复杂度同BFS一致。
第三步实现并优化代码：
老规矩Java你牛你先来：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            int levelMaxValue = Integer.MIN_VALUE;
            for (int i = 0; i < queueSize; i++) {
                TreeNode node = queue.poll();
                levelMaxValue = Math.max(levelMaxValue, node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            result.add(levelMaxValue);
        }
        return result;
    }
}

接着是Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque
import sys

class Solution(object):
    def largestValues(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        result = []
        queue = deque()
        visited = set()
        queue.append(root)

        while queue:
            queue_size = len(queue)
            level_max_value = -sys.maxsize
            for i in range(queue_size):
                node = queue.popleft()
                visited.add(node)
                level_max_value = max(level_max_value, node.val)

                if node.left and node.left not in visited:
                    queue.append(node.left)
                if node.right and node.right not in visited:
                    queue.append(node.right)
            result.append(level_max_value)
        return result

这里对比标准的BFS会发现形式基本一致，只是在while循环体内显式的加入按层遍历的for循环，这是由题目的要求决定的。好吧，问题到这里似乎有了好的解决，回过头来想想DFS是不是也可以实现一下呢？这里先挖个坑，各位有兴趣的可以选择性填下。