130. 被围绕的区域 Krains 2020-08-11 10:50:01 并查集DFS
130. 被围绕的区域 Krains 2020-08-11 10:50:01 并查集DFS
Krains
发布于 2020-08-12 10:07:22
发布于 2020-08-12 10:07:22
# 题目链接
DFS
解题思路
从边缘的'O'出发，用dfs将所有与边缘相邻的'O'改成'A'，未与边缘相邻的'O'将不会改变，然后遍历矩阵，将所有的'A'改成'O'，所有的'O'改成'X'
错误思路
从里边的'O'出发，用dfs将所有相邻的'O'改成'X'，如果搜索过程中碰到了边缘的'O'，则回溯。这个思路错就错在回溯只能将一条到边缘'O'的路径还原，并不能还原其他走向“死胡同”的'O'。
class Solution {
int[][] d = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int m;
int n;
public void solve(char[][] board) {
m = board.length;
if(m == 0)
return;
n = board[0].length;
// 从上下左右四个边缘出发
for(int i = 0; i < n; i++){
dfs(board, 0, i);
dfs(board, m-1, i);
}
for(int i = 0; i < m; i++){
dfs(board, i, 0);
dfs(board, i, n-1);
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(board[i][j] == 'A')
board[i][j] = 'O';
else if(board[i][j] == 'O')
board[i][j] = 'X';
}
}
}
private void dfs(char[][] board, int x, int y){
if(x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O')
return ;
board[x][y] = 'A';
for(int i = 0; i < 4; i++)
dfs(board, x + d[i][0], y + d[i][1]);
}
}
BFS
与dfs思路相同，bfs的版本
class Solution {
int[][] d = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int m;
int n;
public void solve(char[][] board) {
m = board.length;
if(m == 0)
return;
n = board[0].length;
Deque<int[]> queue = new LinkedList<>();
for(int i = 0; i < n; i++){
if(board[0][i] == 'O')
queue.add(new int[]{0, i});
if(board[m-1][i] == 'O')
queue.add(new int[]{m-1, i});
}
for(int i = 1; i < m-1; i++){
if(board[i][0] == 'O')
queue.add(new int[]{i, 0});
if(board[i][n-1] == 'O')
queue.add(new int[]{i, n-1});
}
while(!queue.isEmpty()){
int[] t = queue.remove();
board[t[0]][t[1]] = 'A';
for(int i = 0; i < 4; i++){
int x = t[0] + d[i][0];
int y = t[1] + d[i][1];
if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){
queue.add(new int[]{x, y});
}
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(board[i][j] == 'A')
board[i][j] = 'O';
else if(board[i][j] == 'O')
board[i][j] = 'X';
}
}
}
}并查集
解题思路
- 将各个坐标映射到一维，范围在
[0, m*n-1]，同时定义一个超级源点m*n，这个源点与所有边缘的'O'相连 - 对于在里边的'O'来说，将其与上下左右四个方向的'O'连接起来
- 最后在遍历一遍矩阵，将没有与src连接在一块的'O'置为'X'
class Solution {
// 定义并查集
class UnionFind{
int[] parents;
UnionFind(int size){
parents = new int[size];
for(int i = 0; i < size; i++)
parents[i] = i;
}
public int find(int x){
if(parents[x] == x)
return x;
return parents[x] = find(parents[x]);
}
public void union(int x, int y){
int px = find(x);
int py = find(y);
if(px == py)
return ;
parents[px] = py;
}
public boolean isConnect(int x, int y){
return find(x) == find(y);
}
}
int[][] d = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int m;
int n;
public void solve(char[][] board) {
m = board.length;
if(m == 0)
return;
n = board[0].length;
int size = m * n + 1;
int src = m * n;
UnionFind u = new UnionFind(size);
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(board[i][j] == 'X')
continue;
// 将边缘的'O'与超级源点src相连接
if(i == 0 || i == m-1 || j == 0 || j == n-1)
u.union(src, i * n + j);
else{
// 将周围的'O'与(i, j)连接
for(int k = 0; k < 4; k++){
int x = i + d[k][0];
int y = j + d[k][1];
if(board[x][y] == 'O')
u.union(i * n + j , x * n + y);
}
}
}
}
for(int i = 1; i < m-1; i++){
for(int j = 1; j < n-1; j++){
if(board[i][j] == 'O' && !u.isConnect(src, i * n + j)){
board[i][j] = 'X';
}
}
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-08-11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录