78 DFS和BFS解被围绕的区域

发布时间:2023年12月29日

问题描述:给定一个二维矩阵,包含‘X’和'O',找到所有被X围绕的区域,并将这些区域力所有的O用X来填充。

问题分析:直接查找被包围的O不太好找,只要所有外层都是X,则一定被包围,反之若在边界,与之相连的一定不被包围,

DFS求解:外层大循环是遍历二维矩阵的边界,一旦为O则进入下一层循环中,并定义一个矩阵用来保存已经走过的O区域。

public void? dfs(int[][]matrix,int row,int column,Boolean [][]visited)
{
if(row>matrix.length||row<0||column>matrix[0].length||column<0){return;}
if(visited[row][column]){return;}
if(matrix[row][column]=='O')
{
visited[row][column]=true;
dfs(matrix,row+1,column,Ozero,visited);
dfs(matrix,row-1,column,Ozero,visited);
dfs(matrix,row,column+1,Ozero,visited);
dfs(matrix,row,column-1,Ozero,visited);
}
}

public int[][] FillZero(int [][]matrix)
{
Boolea [][]visited=new Boolean[matrix.length][matrix[0].length];

for(int i=0;i<matrix.length;i++)
{
Arrays.fill(visited[i],false);

}
for(int i=0;i<matrix.length;i++)
{
for(int j=0;j<matrix[i].length;j++)
{
if(i==0||i==matrix.length-1||j==0||j==matrix[0].length)
{
dfs(matrix,i,j,visited);
}
else{
continue;
}
}
}
for(int i=0;i<matrix.length;i++)
{
for(in j=0;j<matrix[0].length;j++)
{
if(visited[i][j]){continue;}
else{matrix[i][j]='X';}
}
}
???????return matrix;
}


BFS求解:将所有确定不围着,且没有访问过的元素放入队列之中,并每次弹出来遍历,如果周围四个元素不越界、是O、且没有被访问过,则标记其被访问,并放入队列中。

public int[][] bfs(int [][]matrix)
{

Boolea [][]visited=new Boolean[matrix.length][matrix[0].length];
for(int i=0;i<matrix.length;i++)
{
Arrays.fill(visited[i],false);

}
//该数组是来判断是O且不能围成的区域。
Queue<Integer>queueRow=new LinkedList<>();
Queue<Integer>queueColumn=new LinkedList<>();
for(int i=0;i<matrix.length;i++)
{
for(int j=0;j<matrix[i].length;j++)
{
if(i==0||i==matrix.length-1||j==0||j==matrix[0].length)
{
queueRow.add(i);
queueColumn.add(j);
visited[i][j]=true;

}
}
}
while(!queueRow.isEmpty())
{
int rowIndex=queueRow.poll();
int colIndex=queueColumn.poll();
if(rowIndex+1<matrix.length&&visited[rowIndex+1][colIndex]==false&&matrix[rowIndex+1][colIndex]=='O'){visited[rowIndex+1][colIndex]=true;queueRow.add(rowIndex+1);queueColumn.add(column);}

if(0<rowIndex-1&&visited[rowIndex-1][colIndex]==false&&matrix[rowIndex-1][colIndex]=='O'){visited[rowIndex-1][colIndex]=true;queueRow.add(rowIndex-1);queueColumn.add(column);}


if(colIndex+1<matrix[0].length&&visited[rowIndex][colIndex+1]==false&&matrix[rowIndex][colIndex+1]=='O'){visited[rowIndex][colIndex+1]=true;queueRow.add(rowIndex);queueColumn.add(column+1);}

if(0<colIndex-1&&visited[rowIndex][colIndex-1]==false&&matrix[rowIndex][colIndex-1]=='O'){visited[rowIndex][colIndex-1]=true;queueRow.add(rowIndex);queueColumn.add(column-1);}
}

for(int i=0;i<matrix.length;i++)
{
for(in j=0;j<matrix[0].length;j++)
{
if(visited[i][j]){continue;}
else{matrix[i][j]='X';}
}
???????return matrix;
}

}

文章来源:https://blog.csdn.net/qq_52299902/article/details/135294704
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。