网站手机站怎么做,网页制作与网站建设设计价格,网站开发过程及要求,上海网站企业floodfill算法二 1.被围绕的区域2.太平洋大西洋水流问题3.扫雷游戏4.衣橱整理 点赞#x1f44d;#x1f44d;收藏#x1f31f;#x1f31f;关注#x1f496;#x1f496; 你的支持是对我最大的鼓励#xff0c;我们一起努力吧!#x1f603;#x1f603; 1.被围绕的区域… floodfill算法二 1.被围绕的区域2.太平洋大西洋水流问题3.扫雷游戏4.衣橱整理 点赞收藏关注 你的支持是对我最大的鼓励我们一起努力吧! 1.被围绕的区域
题目链接130. 被围绕的区域
题目分析 把被X上下左右围绕的O区域变成X注意这个O不能处于边界因为处于边界的O并不会被X上下左右围绕。
算法原理
对于这个例子我们仅需把画绿线的区域修改成X就行了。
解法一直接去做有困难
我们刚开始拿到这道题直接解决这个问题还是以前一样一行一行扫描遇到O了就深度优先遍历一次把与它相连的连通块全部都给成X。但是你碰到紫色的O你深度优先遍历把这些区域都改成X但是这些区域是不能修改的
此时可以这样搞碰到绿色区域深度优先遍历可以改当碰到紫色区域的O也就说这个连通块处于边界的情况递归碰到边界是不仅不能改还需要考虑回溯把改的地方给还原回来。但是你会发现代码非常难些。因为这两个区域的深搜是不一样的要写两种dfs。更致命的问题是我们是在搜索的过程中才发现一个位置是非法的。所以说并不知道这两个区域到底用那个dfs
所以这样搞挺困难的 解法二正难则反 如果直接去搞比较难我可以反着来 这个问题与边界相连的O区域比较难搞此时就能先把处于边界区域的O先处理一下。那剩下的O就自然在内部了。
那边界怎么处理呢我们只要扫描边界就可以了当碰到O就从这个位置来一次dfs可以把与这个位置相连的O位置标记一下。标记有两种策略一搞一个vis数组。二修改原始值 把边界这些 O 修改成 . 。然后把边界情况处理完之后在扫描整个矩阵当碰到 . 就把它还原成一个 O当碰到 O 修改成 X。这样就完美的解决这个问题了。
class Solution {int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};int m,n;
public:void solve(vectorvectorchar board) {mboard.size(),nboard[0].size();// 1.把边界的 O 相连的连通块,全部修改成 .for(int i 0; i m; i)for (int j 0; j n; j)if(board[i][j] O)if(i 0 || i m-1 || j 0 || j n-1) dfs(board,i,j);// 2.还原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;}}void dfs(vectorvectorchar 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);}}}
};2.太平洋大西洋水流问题
题目链接417. 太平洋大西洋水流问题
题目分析 题目描述很难懂这里我们简单说一下。有一个mxn的矩阵这个矩阵相当于一个岛屿。这个岛屿被两个洋包围其中上和左被太平洋包围。下和右被大西洋包围。这个岛屿被分成一块一块的。其中数字代表这一块的高度。此时如果有水的话水是可以从较高的地方流向较低的地方还可以流向和在我周围并且和我相等高度的地方。注意只能上下左右流动。然后题目要求在所有的小格子里能否存在一个位置这个位置的水既可以流向太平洋又可以流向大西洋。如果可以就把这个位置坐标存下来最后返回。最终找到的就是这个岛屿中所有即可流向太平洋又可以流向大西洋的小格子。 算法原理
把题目搞懂了你可能里面会想到把所有小格子枚举一遍。遇到一个点就去看这个位置能不能去大西洋和太平洋。如果可以就加入到最终结果。然后在去下一个位置。
解法一直接判断某一个位置能否去大西洋和太平洋 但是这种直接判断的方式会存在非常多的重复路径一旦矩阵规模很大这样搞可能会超时。因此我们不能直接解决这个问题。拿到一个点就暴力去判断能不能去大西洋和太平洋。我们要换一种方法来解决这个问题。
解法二正难则反
我们要找的是某个位置能不能流向太平洋和大西洋那我能不能反过来过看大西洋和太平洋能否流到相同的位置比如说先看太平洋 上左两条边界开始 水能流向那些位置。如果我反向能从太平洋流向某个位置那这个位置正向也一定能从这个位置流向太平洋。正向是从某个位置流向小于或者等于我的位置。那反向就是流向大于或者等于我的位置。
比如从1开始一次就可以找到有这么多位置可以从1流向太平洋。然后在上面这一行下一个位置但是因为1已经把这些位置标记了所以不会在进去了。这一行都直接结束了。 然后考虑左边这一列没有被标记的地方我可以去。被标记的地方我都不用去了。因为遍历过的地方只会遍历一次所以时间复杂度会降的非常多。
我们反着从最上面一行最左边一列找的这些点都可以流向太平洋。 同理从最下面一行和最右边一列找大西洋能流向那些位置。然后你就会发现有一些重复标记的位置。而这些重复标记的位置就是既能流向太平洋又能流向大西洋。 class Solution {int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};int m,n;
public:vectorvectorint pacificAtlantic(vectorvectorint heights) {mheights.size(),nheights[0].size();vectorvectorbool pac(m,vectorbool(n));vectorvectorbool atl(m,vectorbool(n));// 1. Pacific Ocean for(int j 0; j n; j)dfs(heights,0,j,pac);for(int i 0; i m; i)dfs(heights,i,0,pac);// 2. Atlantic Oceanfor(int j 0; j n; j)dfs(heights,m-1,j,atl);for(int i 0; i m; i)dfs(heights,i,n-1,atl);vectorvectorint ret;// 3. 找重叠for(int i 0; i m; i){for(int j 0; j n; j){if(pac[i][j] atl[i][j])ret.push_back({i,j});}}return ret;}void dfs(vectorvectorint h, int i, int j,vectorvectorbool vis){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] h[x][y] h[i][j]){dfs(h, x, y,vis);}}}};3.扫雷游戏
题目链接529. 扫雷游戏
题目分析 这题说的很多其实就是给一个mxn的棋盘再给一个棋盘坐标点击这个坐标把修改后的棋盘返回。
我们要注意一下规则
‘M’ 代表一个 未挖出的 地雷 ‘E’ 代表一个 未挖出的 空方块 ‘B’ 代表没有相邻上下左右和所有4个对角线地雷的 已挖出的 空白方块
前面我们都只研究上下左右这里还要考虑斜对角线4个位置。也就是说如果当前被挖的空格周围没有地理就把它标记成B。
数字‘1’ 到 ‘8’表示有多少地雷与这块 已挖出的 方块相邻
数字表示这个被挖的格子周围有多少个地雷
‘X’ 则表示一个 已挖出的 地雷。
根据以下规则返回相应位置被点击后对应的盘面
如果一个地雷‘M’被挖出游戏就结束了- 把它改为 ‘X’ 。
也就是说如果刚开始给你的这个位置就是雷的话把这个位置改成‘X’直接结束即可
如果一个 没有相邻地雷 的空方块‘E’被挖出修改它为‘B’并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
如果当前被挖的位置周围没有地雷把它改成’B‘然后递归的往周围走。
如果一个 至少与一个地雷相邻 的空方块‘E’被挖出修改它为数字‘1’ 到 ‘8’ 表示相邻地雷的数量。
如果当前被挖的位置周围有地雷把它修改成周围的地雷数然后就不要递归下去了。直接返回。
如果在此次点击中若无更多方块可被揭露则返回盘面。
算法原理
其实这就是一个模拟已经告诉怎么去操作了。
当点击这个位置之后我们要先统计一下点击的这个位置周围有没有地雷。周围没有地雷就把这个位置改成’B‘然后递归的把周围所有位置都找一遍。如果周围有地雷的话就把这个位置改成地雷数然后就不要从这个位置在递归下去了返回即可。同理递归进去也是如上面一样先统计周围有没有地雷。。。。
不过这里有个细节问题我们之前是沿着一个位置上下左右找4个位置。但是这个位置要找一圈8个位置。我们还是和之前一样我们直接把向量数组扩展一下就可以了。可以写两个-11之后然后给它们分别匹配-11。 class Solution
{int dx[8]{0, 0, 1, -1, -1, -1, 1, 1};int dy[8]{1, -1, 0, 0, -1, 1, -1, 1};int m,n;
public:vectorvectorchar updateBoard(vectorvectorchar board, vectorint click) {int iclick[0],jclick[1];if(board[i][j] M) //直接点到地雷{board[i][j]X;return board;}mboard.size(),nboard[0].size();dfs(board,i,j);return board;}void dfs(vectorvectorchar board, int i, int j){int cnt0;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){if(board[x][y] M) cnt;}}if(cnt) //周围有地雷{board[i][j]0cnt;return;}else //周围没地理{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);}}}}
};4.衣橱整理
题目链接 LCR 130. 衣橱整理
题目分析 有一个mxn的格子从下标00出发注意可以整理的格子横坐标和纵坐标位数和要小于等于cnt。当 cnt 为 19时能够进入方格 [35, 37] 因为 353718。但它不能进入方格 [35, 38]因为 353819统计一下总共可以整理多少个格子。
算法原理 从开始位置来一次深度优先遍历把能进入格子的个数统计一下就行。其实就是一步floodfill算法也就是一次深度优先遍历把相同性质的格子个数找出来数位之和小于等于cnt。
class Solution {bool vis[101][101];int dx[2]{0,1};int dy[2]{1,0};int m,n,cnt;int count0;
public:int wardrobeFinishing(int _m, int _n, int _cnt) {m_m,n_n,cnt_cnt;dfs(0,0);return count;}void dfs(int i, int j){count;vis[i][j]true;for(int k 0; k 2; k){int x i dx[k], y j dy[k];if(x 0 x m y 0 y n !vis[x][y] check(x, y)){dfs(x,y);}}}bool check(int i, int j){int sum0;while(i){sum i % 10;i / 10;}while(j){sum j %10;j / 10;}return sum cnt;}
};
