电商网站人员配置,十大网络舆情案例,怎么做企业网站,上海民政网站相关建设情况题目链接 Leetcode.130 被围绕的区域 mid 题目描述
给你一个 m x n的矩阵 board#xff0c;由若干字符 X和 O#xff0c;找到所有被 X围绕的区域#xff0c;并将这些区域里所有的 O用 X填充。
示例 1#xff1a; 输入#xff1a;board [[“X”,“X”,“X”,“X”],[“X…题目链接 Leetcode.130 被围绕的区域 mid 题目描述
给你一个 m x n的矩阵 board由若干字符 X和 O找到所有被 X围绕的区域并将这些区域里所有的 O用 X填充。
示例 1 输入board [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]] 输出[[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]] 解释被围绕的区间不会存在于边界上换句话说任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻则称它们是“相连”的。 示例 2 输入board [[“X”]] 输出[[“X”]] 提示
mboard.lengthm board.lengthmboard.lengthnboard[i].lengthn board[i].lengthnboard[i].length1m,n2001 m, n 2001m,n200board[i][j]为 X或 O
解法dfs
我们先从 boardboardboard 的四周与边界相邻的 board[i][j]board[i][j] board[i][j] ’O的区域记录下来这些区域是不能被 X填充的。
接着剩下的 board[i][j]board[i][j] board[i][j] ’O的区域才是能被 X填充的。
时间复杂度 O(mn)O(mn)O(mn)
C代码 class Solution {
public:void solve(vectorvectorchar g) {int m g.size() , n g[0].size();//记录是否被访问过bool vis[m][n];memset(vis,false,sizeof vis);functionvoid(int ,int,bool) dfs [](int i,int j,bool mode) - void{if(i 0 || i m || j 0 || j n || vis[i][j]) return;if(g[i][j] X) return;vis[i][j] true;if(mode) g[i][j] X;dfs(i 1,j,mode);dfs(i - 1,j,mode);dfs(i,j 1,mode);dfs(i,j - 1,mode);};//记录从左右两边开始的 不能被 X 填充的位置for(int i 0;i m;i){if(g[i][0] O !vis[i][0]) dfs(i,0,false);if(g[i][n-1] O !vis[i][n-1]) dfs(i,n-1,false);}//记录从上下两边开始的 不能被 X 填充的位置for(int j 0;j n;j){if(g[0][j] O !vis[0][j]) dfs(0,j,false);if(g[m-1][j] O !vis[m-1][j]) dfs(m-1,j,false);}//剩下的 g[i][j] O 并且没有被访问过的位置 都可以被 X填充for(int i 1;i m - 1;i){for(int j 1;j n - 1;j){if(g[i][j] O !vis[i][j]) dfs(i,j,true);}}}
};
