给定一个二维的矩阵,包含 'X' 和 'O'(字母 O)。
找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。
示例:
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'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
这道题有三种解法,可以用dfs或者bfs或者并查集来做
使用bfs或者dfs思路:
开一个二维布尔数组,记录哪些区域被遍历过。
枚举所有边界上的'O',从该位置做bfs或者dfs,只遍历是'O'的位置,并将所有遍历到的位置都标记成true。
将所有未遍历到的位置变成'X'。
1.dfs
boolean [][]visited;
int row,col;
public void solve(char[][] board) {
row = board.length;
if (row==0){
return;
}
col = board[0].length;
visited = new boolean[row][col];
for (int i =0;i<row;i++){
if (board[i][0]=='O') dfs(i,0,board);
if (board[i][col-1]=='O') dfs(i,col-1,board);
}
for (int i=0;i<col;i++){
if (board[0][i]=='O') dfs(0,i,board);
if (board[row-1][i]=='O') dfs(row-1,i,board);
}
for (int i=0;i<row;i++){
for (int j=0;j<col;j++){
if (!visited[i][j]){
board[i][j] = 'X';
}
}
}
}
public void dfs(int x,int y,char[][]board){
visited[x][y] = true;
int dx[] = {-1,0,1,0}; int dy[] = {0,1,0,-1};
for (int i=0;i<4;i++){
int a = x + dx[i];
int b = y + dy[i];
if (a>=0&&a<row&&b>=0&&b<col&&!visited[a][b]&&board[a][b]=='O'){
dfs(a,b,board);
}
}
}
2.bfs
//bfs 做法
boolean [][]visited;
int row,col;
public void solve2(char[][]board){
int row = board.length;
if (row==0) return;
int col = board[0].length;
visited = new boolean[row][col];
Queue<Pair<Integer,Integer>> queue = new LinkedList<>();
for (int i=0;i<row;i++){
if (board[i][0]=='O'){
visited[i][0] = true;
Pair<Integer,Integer> pair = new Pair<>(i,0);
queue.add(pair);
}
if (board[i][col-1]=='O'){
visited[i][col-1] = true;
Pair<Integer,Integer> pair = new Pair<>(i,col-1);
queue.add(pair);
}
}
for (int i=0;i<col;i++){
if (board[0][i]=='O'){
visited[0][i] = true;
Pair<Integer,Integer> pair = new Pair<>(0,i);
queue.add(pair);
}
if (board[row-1][i]=='O'){
visited[row-1][i] = true;
Pair<Integer,Integer> pair = new Pair<>(row-1,i);
queue.add(pair);
}
}
int dx[] = {-1,0,1,0}, dy[]={0,1,0,-1};
while (!queue.isEmpty()){
Pair <Integer,Integer> pair = queue.poll();
int x = pair.getKey();
int y = pair.getValue();
visited[x][y] = true;
for (int i=0;i<4;i++){
int a = x + dx[i];
int b = y + dy[i];
if (a>=0&&a<row&&b>=0&&b<col&&!visited[a][b]&&board[a][b]=='O'){
queue.add(new Pair(a,b));
}
}
}
for (int i=0;i<row;i++){
for (int j = 0;j<col;j++){
if (!visited[i][j]){
board[i][j] = 'X';
}
}
}
}
3.并查集做法 思路:把所有不被'X'包围的'O'放在同一个集合里,然后遍历数组,将不在集合中的'O'转换为'X'。
//并查集做法
int[] parent ;
int rows,cols;
final int manx = 100005;
int find(int x){
while (x!=parent[x]){
x = parent[x];
}
return x;
}
void Union(int x,int y){
x = find(x);
y = find(y);
if (x > y){
parent[x] = y;
}else if (x < y){
parent[y] = x;
}
}
boolean same(int x,int y){
return find(x)==find(y);
}
public void solve3(char[][]board){
rows = board.length;
if (rows==0) return;
cols = board[0].length;
parent = new int[manx];
for (int i=0;i<manx;i++){
parent[i] = i;
}
int dx[] = {-1,0,1,0}, dy[]={0,1,0,-1};
for (int i=0;i<rows;i++){
for (int j=0;j<cols;j++){
if ((i==0 || i==rows-1 || j==0 || j==cols-1) && board[i][j]=='O'){
Union(i*rows+j,rows*cols);
}else if (board[i][j]=='O'){
for (int k =0;k<4;k++){
int x = i + dx[k];
int y = j + dy[k];
if (board[x][y]=='O'){
Union(i*rows+j,x*rows+y);
}
}
}
}
}
for (int i=0;i<rows;i++){
for (int j =0;j<cols;j++){
if (!same(i*rows+j,rows*cols)) board[i][j] = 'X';
}
}
}
网友评论