【算法】【floodfill】洪水灌溉

1. 岛屿数量

👉🔗题目链接

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

几个注意点：

1. 二维深搜，巧妙使用全局方向矩阵
2. 状态表记录，可以不改动原表
3. 在搜索时注意 边界值 + 条件！！！

class Solution {
public:
    vector<vector<bool>> vis;
    int m, n;

    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        vis = vector<vector<bool>>(m, vector<bool>(n));
        int count = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == '1' && !vis[i][j])
                {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }

        return count;
    }

    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    
    void dfs(const vector<vector<char>>& grid, int i, int j)
    {
        vis[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])
            {
                dfs(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
35
36
37
38
39
40

---

2. 岛屿最大面积

👉🔗题目链接

给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

和上述代码雷同！仔细设计一下哪些做全局变量吧~

---

3. 被围绕的区域

👉🔗题目链接

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充

和上述的题目相似，但有差别！
在边界上出现的 ‘O’ 不能计入，如果还使用之前的方法，在触碰边界条件的时候回退，代码逻辑编写起来是有困难的！怎么办呢?

正着写麻烦，就反着来吧。

先解决所有边界上的值，周围一圈的值，碰到一个 ‘O’ 就深搜一下，修改成 ‘+’。再把里面的都修改成 ‘X’ 不就解决啦！

class Solution {
public:
    int m, n;
    
    void solve(vector<vector<char>>& board) {
        m = board.size();
        n = board[0].size();
        // 1.将外面一圈的O相连的连通块,都处理了
        for(int i = 0; i < m; i++)
        {
            if(board[i][0] == 'O') dfs(board, i, 0);
            if(board[i][n-1] == 'O') dfs(board, i, n-1);
        }
        for(int j = 0; j < n; j++)
        {
            if(board[0][j] == 'O') dfs(board, 0, j);
            if(board[m-1][j] == 'O') dfs(board, m-1, j);
        }
        // 2.还原：将O都改成X，将+都改成O
        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] == '+')	
                    board[i][j] = 'O';
            }   
    }

    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    // 把与进入位置相连的块都改成+
    void dfs(vector<vector<char>>& board, int i, int j)
    {
        board[i][j] = '+';
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
                dfs(board, 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
35
36
37
38
39
40
41
42
43

---

4. 太平洋大西洋水流问题

👉🔗题目链接

手动翻译一下脑残的题目：给出的矩阵中，每个数字是高于海平面的高度。水可以从高处往低处流，也可以往相同高度流，矩阵边界的水都可以往海里流。按照他给出的两个海的位置，返回一系列[x, y]位置，要求这些位置上的水，既可以流向大西洋也可以流向太平洋。(图中橙色标记的格子的 index 就是满足条件的，也就是需要返回的)

解法1：

• 暴力解法，对每一个格子进行判断，既能到左上，又能到右下则加入返回集合。
• 逻辑比较好写，就是有很多重复路径，不太聪明（sos

解法2：

• 正难则反
• 从边界开始反推，哪些地方的水是可以流向太平洋 / 大西洋的！
• 最后两边一汇总就是最后可以输出的结果。

class Solution {
public:
    int m, n;

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size();
        n = heights[0].size();
        vector<vector<bool>> pac(m, vector<bool>(n));
        vector<vector<bool>> ath(m, vector<bool>(n));
        vector<vector<int>> ret;

        // 1.填充两张状态表
        for(int i = 0; i < m; i++)
        {
            // 太平洋:左
            if(!pac[i][0]) dfs(heights, i, 0, pac);
            // 大西洋:右
            if(!ath[i][n-1]) dfs(heights, i, n-1, ath);
        }
        for(int j = 0; j < n; j++)
        {
            // 太平洋: 上
            if(!pac[0][j]) dfs(heights, 0, j, pac);
            // 大西洋: 下
            if(!ath[m-1][j]) dfs(heights, m-1, j, ath);
        }

        // 2.找出重合坐标
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(pac[i][j] && ath[i][j])
                    ret.push_back(vector<int>{i,j});

        return ret;
    }

    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};

    void dfs(const vector<vector<int>>& heights, int i, int j, vector<vector<bool>>& status)
    {
        status[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && heights[x][y] >= heights[i][j] && !status[x][y])
                dfs(heights, x, y, status);
        }
    }
};
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
38
39
40
41
42
43
44
45
46
47
48
49
50

---

5. 扫雷游戏

👉🔗题目链接

• ‘M’ 代表一个 未挖出的 地雷，
• ‘E’ 代表一个 未挖出的 空方块，
• ‘B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块， 数字（‘1’ 到 ‘8’）表示有多少地雷与这块已挖出的 方块相邻， ‘X’ 则表示一个 已挖出的 地雷。 给你一个整数数组 click ，其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（‘M’ 或者 ‘E’）中的下一个点击位置（clickr 是行下标，clickc 是列下标）。

根据以下规则，返回相应位置被点击后对应的盘面：

• 如果一个地雷（‘M’）被挖出，游戏就结束了- 把它改为 ‘X’ 。
• 如果一个 没有相邻地雷 的空方块（‘E’）被挖出，修改它为（‘B’），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
• 如果一个 至少与一个地雷相邻 的空方块（‘E’）被挖出，修改它为数字（‘1’ 到 ‘8’ ），表示相邻地雷的数量。
• 如果在此次点击中，若无更多方块可被揭露，则返回盘面。

👉🔗游戏链接

class Solution {
public:
    int m, n;
    int dx[8] = {0,0,1,-1,1,1,-1,-1};
    int dy[8] = {1,-1,0,0,1,-1,1,-1};
    
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size();
        n = board[0].size();
        int i = click[0];
        int j = click[1];
        
        // 是地雷
        if(board[i][j] == 'M') 
        {
            board[i][j] = 'X';
            return board;
        }
        // 不是地雷
        dfs(board, i, j);

        return board;
    }

    void dfs(vector<vector<char>>& board, int i, int j)
    {


        // 先判断一下周围的地雷数
        int count = 0;
        for(int k = 0; k < 8; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >=0 && y < n && board[x][y] == 'M')
                count++;
        }
        // 周围有地雷
        if(count)
        {
            board[i][j] = '0' + count;
            return;
        }

        // 没有地雷
        board[i][j] = 'B';
        for(int k = 0; k < 8; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
                dfs(board, 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

能少走两次 count_and_modify_M 的写法：

class Solution {
public:
    int m, n;
    int dx[8] = {0,0,1,-1,1,1,-1,-1};
    int dy[8] = {1,-1,0,0,1,-1,1,-1};
    
    // 求 i,j 位置一周地雷的个数，如果有地雷，则修改board
    int count_and_modify_M (vector<vector<char>>& board, int i, int j)
    {
        int count = 0;
        for(int k = 0; k < 8; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >=0 && y < n && board[x][y] == 'M')
                count++;
        }
        if(count > 0)
            board[i][j] = '0' + count;
        return count;
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size();
        n = board[0].size();
        int i = click[0];
        int j = click[1];
        
        // 是地雷
        if(board[i][j] == 'M') 
        {
            board[i][j] = 'X';
            return board;
        }

        // 是已经挖开的
        if(board[i][j] == 'B' || (board[i][j] >= '0'+ 1 && board[i][j] <= '0'+ 8))
            return board;

        // 是挨着地雷的
        if(count_and_modify_M(board, i, j) != 0)
            return board;

        // 进入递归并判断
        dfs(board, i, j);

        return board;
    }

    void dfs(vector<vector<char>>& board, int i, int j)
    {
        board[i][j] = 'B'; 
        
        for(int k = 0; k < 8; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n 
                && (board[x][y] == 'E' || board[x][y] == 'M') 
                && count_and_modify_M(board, x, y) == 0)
                dfs(board, 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

---

6. 机器人的运动范围

👉🔗题目链接

地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？

拿到题目，别被数位之和唬住了。

机器人能走的路径是连续的，这里也就是从(0,0)开始，一次深搜的事儿，数位之和只是一个边界条件嘛！

#include 
#include 
using namespace std;
class Solution 
{
public:
    int m, n, k, ret = 0;
    vector<vector<bool>> vis;

    int movingCount(int threshold, int rows, int cols) 
    {
        m = rows, n = cols, k = threshold;
        vis = vector<vector<bool>>(m, vector<bool>(n));
        dfs(0, 0);
        return ret;   
    }

    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};

    void dfs(int i, int j)
    {     
        ret++;
        vis[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && is_accessible(x, y))
                dfs(x, y);
        }
    }

    bool is_accessible(int x, int y)
    {
        int sum = 0;
        while(x)
        {
            sum += x % 10;
            x /= 10;
        }
        while(y)
        {
            sum += y % 10;
            y /= 10;
        }
        if(sum <= k)
            return true;
        return false;
    }
};
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
38
39
40
41
42
43
44
45
46
47
48
49
50

---

🥰如果本文对你有些帮助，欢迎👉 点赞 收藏 关注，你的支持是对作者大大莫大的鼓励！！(✿◡‿◡) 若有差错恳请留言指正~~

---