题目描述
给定一个二维的矩阵，包含 ‘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’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
分析
对于题意是很容易理解的，也就是只有和边缘连接的O不会被 X 包围，其他都会被X包围。
这是一道图论搜索题，核心的处理思路就是找矩阵所有边缘开始，如果是x那么跳过，如果是o那么开始查找与该点上下左右联通的点进行标记(被标记则证明没有被包围)。那么最终剩下没有被标记的节点就是保留o。其他节点全部变成x.
在具体处理上dfs或者bfs都可以，向四周遍历时候记得不能出界。
具体代码：
class Solution { int X[]={0,1,0,-1}; int Y[]={1,0,-1,0}; public void solve(char[][] board) { int lenx=board.length,leny=board[0].length; boolean jud[][]=new boolean[lenx][leny]; for(int i=0;i<lenx;i++)//两个竖得 { if(board[i][0]=='O'&&!jud[i][0]) { judgle(i,0,board,jud); jud[i][0]=true; } if(board[i][leny-1]=='O'&&!jud[i][leny-1]) { judgle(i,leny-1,board,jud); jud[i][leny-1]=true; } } for(int i=0;i<leny;i++)//两个横得 { if(board[0][i]=='O'&&!jud[0][i]) { judgle(0,i,board,jud); jud[0][i]=true; } if(board[lenx-1][i]=='O'&&!jud[lenx-1][i]) { judgle(lenx-1,i,board,jud); jud[lenx-1][i]=true; } } for(int i=0;i<lenx;i++) { for(int j=0;j<leny;j++) { if(!jud[i][j]) { board[i][j]='X'; } } } } private void judgle(int x, int y, char[][] board, boolean[][] jud) { // TODO Auto-generated method stub for(int i=0;i<4;i++) { int x1=x+X[i]; int y1=y+Y[i]; if(x1>=0&&x1<board.length&&y1>=0&&y1<board[0].length) { if(!jud[x1][y1]&&board[x1][y1]=='O') { jud[x1][y1]=true; judgle(x1, y1, board, jud); } } } } }
咱们下次再见！关注后欢迎加入力扣打卡群(备注力扣 csdn即可)。
