Flood Fill 算法详解：图像渲染与岛屿问题

二、岛屿数量

题目解析

给定一个 n*m 的二维数组，其中 1 表示陆地、0 表示海洋；多个相邻的陆地可以看做是一座岛屿，要求计算网格中岛屿的数量。

算法思路

遍历 grid 数组，遍历到陆地 (1) 并且该陆地没有和其他陆地形成岛屿（没有被 BFS/DFS 遍历过），就从该节点进行一次 BFS/DFS 遍历。这样只需要统计在遍历 grid 时，进行 BFS/DFS 的次数即可。

这里使用 DFS 来解决这道题。

代码实现

class Solution {
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    bool vis[300][300];
public:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        vis[i][j] = true;
        int m = grid.size(), n = grid[0].size();
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == '1')
                dfs(grid, x, y);
        }
    }
    
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !vis[i][j]) {
                    dfs(grid, i, j);
                    ret++;
                }
            }
        }
        return ret;
    }
};

三、岛屿的最大面积

题目解析

算法思路

这道题的解题思路和求岛屿数量大同小异：还是遍历 grid 数组，在遍历到陆地并且该陆地没有和其他陆地组成岛屿（遍历到 1 并且该位置没有被遍历过）时，就从该位置进行一次 BFS 遍历（DFS 也可以解决），并求出岛屿的面积；然后统计岛屿面积的最大值并返回即可。

代码实现

class Solution {
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    bool vis[50][50];
public:
    void dfs(vector<vector<int>>& grid, int i, int j, int& cnt) {
        ++cnt;
        vis[i][j] = true;
        int m = grid.size();
        int n = grid[0].size();
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y])
                dfs(grid, x, y, cnt);
        }
    }
    
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ret = 0, cnt = 0;
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !vis[i][j]) {
                    dfs(grid, i, j, cnt);
                    ret = max(ret, cnt);
                    cnt = 0;
                }
            }
        }
        return ret;
    }
};

四、被围绕的区域

题目解析

算法思路

将所有不在边缘区域的 O 全部修改成 X。

1. 先将在边缘的 O 区域进行标记（特殊处理，修改成其他无关字符）
2. 再将所有没有标记的 O 全部修改成 X
3. 最后，再复原边缘区域的 O

代码实现

class Solution {
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool vis[210][210];
public:
    void dfs(vector<vector<char>>& board, int i, int j, bool isChange = false) {
        if (isChange) board[i][j] = 'X';
        vis[i][j] = true;
        int m = board.size();
        int n = board[0].size();
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && y >= 0 && x < m && y < n && !vis[x][y] && board[x][y] == 'O')
                dfs(board, x, y, isChange);
        }
    }
    
    void solve(vector<vector<char>>& board) {
        // 处理边界
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O' && !vis[i][0]) dfs(board, i, 0);
            if (board[i][n - 1] == 'O' && !vis[i][n - 1]) dfs(board, i, n - 1);
        }
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O' && !vis[0][i]) dfs(board, 0, i);
            if (board[m - 1][i] == 'O' && !vis[m - 1][i]) dfs(board, m - 1, i);
        }
        // 修改内部
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O' && !vis[i][j]) dfs(board, i, j, true);
            }
        }
    }
};