78 DFS和BFS解被围绕的区域

问题描述：给定一个二维矩阵，包含‘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;
}

}