力扣每日一题130：被围绕的区域

本文主要是介绍力扣每日一题130：被围绕的区域，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

中等

相关标签

相关企业

给你一个 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"]]

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] 为 'X' 或 'O'

通过次数 285.7K

提交次数 614.4K

通过率 46.5%

方法一：并查集

利用并查集，将相邻的相同字母视为一个连通集。边界上的'O'视为同一个集，易得，不与边界上的'O'相邻的'O'即为被围绕的区域。

下面是某位大佬的java代码

class UnionFind {int[] parents;public UnionFind(int totalNodes) {parents = new int[totalNodes];for (int i = 0; i < totalNodes; i++) {parents[i] = i;}}// 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.void union(int node1, int node2) {int root1 = find(node1);int root2 = find(node2);if (root1 != root2) {parents[root2] = root1;}}int find(int node) {while (parents[node] != node) {// 当前节点的父节点 指向父节点的父节点.// 保证一个连通区域最终的parents只有一个.parents[node] = parents[parents[node]];node = parents[node];}return node;}boolean isConnected(int node1, int node2) {return find(node1) == find(node2);}
}
class Solution {int rows;int cols;public void solve(char[][] board) {if (board == null || board.length == 0)return;rows = board.length;cols = board[0].length;// 用一个虚拟节点, 边界上的O 的父节点都是这个虚拟节点UnionFind uf = new UnionFind(rows * cols + 1);int dummyNode = rows * cols;for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (board[i][j] == 'O') {// 遇到O进行并查集操作合并if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {// 边界上的O,把它和dummyNode 合并成一个连通区域.uf.union(node(i, j), dummyNode);} else {// 和上下左右合并成一个连通区域.if (i > 0 && board[i - 1][j] == 'O')uf.union(node(i, j), node(i - 1, j));if (i < rows - 1 && board[i + 1][j] == 'O')uf.union(node(i, j), node(i + 1, j));if (j > 0 && board[i][j - 1] == 'O')uf.union(node(i, j), node(i, j - 1));if (j < cols - 1 && board[i][j + 1] == 'O')uf.union(node(i, j), node(i, j + 1));}}}}for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (uf.isConnected(node(i, j), dummyNode)) {// 和dummyNode 在一个连通区域的,那么就是O；board[i][j] = 'O';} else {board[i][j] = 'X';}}}}int node(int i, int j) {return i * cols + j;}}

方法二：深度优先搜索

前面提到，不与边界的'O'连通的'O'即为被包围的区域。所以我们可以以四条边上的'O'为起点搜索，将与边界'O'连通的'O'做个标记，随后有标记的'O'就改回'O'，没有标记的'O'就变成'X'。

class Solution {
public:void dfs(vector<vector<char>>& board,int x,int y,int n,int m){if(x<0||x>=n||y<0||y>=m||board[x][y]!='O'){return;}board[x][y]='Y';dfs(board,x+1,y,n,m);dfs(board,x,y-1,n,m);dfs(board,x-1,y,n,m);dfs(board,x,y+1,n,m);}void solve(vector<vector<char>>& board) {int n=board.size();if(n==1) return;int m=board[0].size();if(m==1) return;for(int i=0;i<n;i++){dfs(board,i,0,n,m);dfs(board,i,m-1,n,m);}for(int j=1;j<m-1;j++){dfs(board,0,j,n,m);dfs(board,n-1,j,n,m);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(board[i][j]=='Y')board[i][j]='O';else if(board[i][j]=='O')board[i][j]='X';}}}
};

这篇关于力扣每日一题130：被围绕的区域的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---