【floodfill深搜】太平洋大西洋水流问题 && 扫雷游戏 &&衣橱整理

利刃大大

发布于 2025-02-13 09:49:40

5400

代码可运行

文章被收录于专栏：csdn文章搬运csdn文章搬运

运行总次数：0

代码可运行

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

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

示例 1：

输入: heights = [[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]]

示例 2：

输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]

提示：

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 105

解题思路：正难则反

刚拿到这道题的时候，第一思路就是想暴力枚举所有的元素，以每个元素为入口进行一次深度优先遍历，并且判断一下是否存在流向大西洋和太平洋的位置，是的话则加入结果集！这个思路确实是可以的，但是在这道题中有规模很大的矩阵，此时就会超时了，因为当我们遍历一个元素进行深度优先遍历之后，我们遍历下一个元素再次进行深度优先遍历的时候，此时可能会重复了之前走过的一些路径，也就是说，我们这种方法存在着大量的重复遍历，导致超时，所以我们必须换个思路！

正难则反，既然我们从高处向低处找路径会超时，那么我们试试从低处往高处找！

不过有一个问题，就是如果我们是从低处往高处找的话，因为我们要找的是流向两个洋的，那么我们 只能从单个洋的低处往上找到高处，所以我们需要分别对太平洋和大西洋的低处开始向上找，而没办法同时处理流向两个洋的情况！

又因为 i = 0 和 j = 0 是太平洋低处的位置，所以我们就从符合这两个坐标的位置处开始向上找流向太平洋的路径，然后用一个布尔值类型的二维数组 pacific_used 标记走过的路径，表示这是可以从高处流向太平洋的路径！

而 i = m - 1 和 j = n - 1（这里 m、n 分别表示岛屿的长和宽）是大西洋低处的位置，我们同样从符合这两个坐标的位置处开始向上找流向大西洋的路径，然后用一个布尔值类型的二维数组 atlantic_used 标记走过的路径，表示这是可以从高处流向大西洋的路径！

此时重点来了，我们遍历两个布尔值数组，判断两个数组中是否存在位置都为 true 的，存在的话说明从这个位置是可以同时流向两个洋，则添加到结果集中，如果不存在的话则不需要处理，最后返回结果集即可！

而对于其中向高处寻找路径的递归函数就不再赘述了，比较简单，就是一些边界条件要处理好，防止越界即可！

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size();
        int n = heights[0].size();

        // 1. 先处理太平洋
        vector<vector<bool>> pacific_used(m, vector<bool>(n, false));
        for(int i = 0; i < m; ++i) dfs(heights, i, 0, pacific_used);
        for(int j = 0; j < n; ++j) dfs(heights, 0, j, pacific_used);
        
        // 2. 再处理大西洋
        vector<vector<bool>> atlantic_used(m, vector<bool>(n, false));
        for(int i = 0; i < m; ++i) dfs(heights, i, n - 1, atlantic_used);
        for(int j = 0; j < n; ++j) dfs(heights, m - 1, j, atlantic_used);
		
        // 3. 判断两个标记数组中是否存在都为true的，是的话说明可以同时流向两个洋，则添加到结果集中
        vector<vector<int>> ret;
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(pacific_used[i][j] && atlantic_used[i][j])
                    ret.push_back({ i, j });
        return ret;
    }

    void dfs(vector<vector<int>>& heights, int x, int y, vector<vector<bool>>& used)
    {
        // 标记为已走过，然后根据边界情况进行递归处理
        used[x][y] = true;
        if(x + 1 < heights.size() && heights[x + 1][y] >= heights[x][y] && used[x + 1][y] == false)
            dfs(heights, x + 1, y, used);
        if(y + 1 < heights[0].size() && heights[x][y + 1] >= heights[x][y] && used[x][y + 1] == false)
            dfs(heights, x, y + 1, used);
        if(x - 1 >= 0 && heights[x - 1][y] >= heights[x][y] && used[x - 1][y] == false)
            dfs(heights, x - 1, y, used);
        if(y - 1 >= 0 && heights[x][y - 1] >= heights[x][y] && used[x][y - 1] == false)
            dfs(heights, x, y - 1, used);
    }
};

529. 扫雷游戏

让我们一起来玩扫雷游戏！

给你一个大小为 m x n 二维字符矩阵 board ，表示扫雷游戏的盘面，其中：

'M' 代表一个 未挖出的 地雷，
'E' 代表一个 未挖出的 空方块，
'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块，
数字（'1' 到 '8'）表示有多少地雷与这块 已挖出的 方块相邻，
'X' 则表示一个 已挖出的 地雷。

给你一个整数数组 click ，其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（'M' 或者 'E'）中的下一个点击位置（clickr 是行下标，clickc 是列下标）。

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

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

示例 1：

输入：board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]], click = [3,0]
输出：[["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

示例 2：

输入：board = [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]], click = [1,2]
输出：[["B","1","E","1","B"],["B","1","X","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 50
board[i][j] 为 'M'、'E'、'B' 或数字 '1' 到 '8' 中的一个
click.length == 2
0 <= clickr < m
0 <= clickc < n
board[clickr][clickc] 为 'M' 或 'E'

解题思路：深度优先遍历 + 模拟

这道题其实难在规则看起来比较杂，但是一旦规则看懂了，其实就是一个模拟题，只不过在模拟题的基础上需要有深度优先遍历操作罢了！这里就不细讲规则了，慢慢读都能读懂！

和前面题目的区别在于这道题因为走的是还没展开的方块，此时就需要根据它外围一圈，包括左上角、右上角、左下角、右下角的方块也要判断，判断有多少个地雷，如果有地雷的话则将当前方块设为地雷的数量（注意是数字字符，不是整型数字），没有的话则可以向外围一圈进行递归处理！

我们前面对于外围一圈只有四个方块来说可以写四个 dfs() 语句，但是这里因为有八个方块需要判断，所以写八个就太麻烦了，所以这里考虑用两个数组 row 和 col，分别代表外围一圈的一对坐标，然后我们只需要遍历数组来进行坐标的累加即可，这样子方便很多！

剩下的其实就是根据规则来走，没什么好说的，具体参考代码：

class Solution {
private:
    int row[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
    int col[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
    int m, n;
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size(), n = board[0].size();
        int x = click[0], y = click[1];

        // 如果点击的是地雷直接就炸了
        if(board[x][y] == 'M')
        {
            board[x][y] = 'X';
            return board;
        }

        dfs(board, x, y);
        return board;
    }

    void dfs(vector<vector<char>>& board, int x, int y)
    {
        // 先统计周围地雷的个数
        int count = 0;
        for(int i = 0; i < 8; ++i)
        {
            int tmpx = x + row[i];
            int tmpy = y + col[i];
            if(tmpx >= 0 && tmpx < m && tmpy >= 0 && tmpy < n && board[tmpx][tmpy] == 'M')
                count++;
        }
        
        // 有地雷的话，设置为地雷个数然后返回即可
        if(count > 0)
        {
            board[x][y] = count + '0';
            return;
        }

        // 没有地雷的话，则设置为B，然后向还没展开的方块进行递归
        board[x][y] = 'B';
        for(int i = 0; i < 8; ++i)
        {
            int tmpx = x + row[i];
            int tmpy = y + col[i];
            if(tmpx >= 0 && tmpx < m && tmpy >= 0 && tmpy < n && board[tmpx][tmpy] == 'E')
                dfs(board, tmpx, tmpy);
        }
    }
};

LCR 130. 衣橱整理

家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。

整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。

请返回整理师 总共需要整理多少个格子。

示例 1：

输入：m = 4, n = 7, cnt = 5
输出：18

提示：

1 <= n, m <= 100
0 <= cnt <= 20

解题思路：深度优先遍历

这道题，其实相比前面几道来说要简单的多，无非就是要多写一个 digit() 函数来获取数字的各数位之和罢了，剩下的就是深搜，遇到不符合条件的就停下来，当然一样需要使用 used 数组来防止重复访问！

class Solution {
private:
    int res = 0;		 // 存放结果集
    bool used[100][100]; // 防止重复访问
public:
    int wardrobeFinishing(int m, int n, int cnt) {
        dfs(m, n, cnt, 0, 0);
        return res;
    }

    void dfs(int m, int n, int cnt, int i, int j)
    {
        // 递归函数出口
        if(i == m || j == n || used[i][j] == true || digit(i) + digit(j) > cnt)
            return;
            
        res++;
        used[i][j] = true;
        dfs(m, n, cnt, i + 1, j);
        dfs(m, n, cnt, i, j + 1);
    }
	
    // 获取数字的各数位之和
    int digit(int n)
    {
        int ret = 0;
        while(n != 0)
        {
            ret += (n % 10);
            n /= 10;
        }
        return ret;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-12，如有侵权请联系 cloudcommunity@tencent.com 删除

数组