第一次在简书上发表文章，感觉有些紧张
这次题目是一个深度搜索的题目
给定一个二维的矩阵，包含'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，将这些O进行标记。
接下来遍历数组，没有被标记的O，就是需要改变成X的O了
最后，再进行一次遍历，将所有被标记的O改回去。
可能有些麻烦，再日后的学习中如果看到新的解法，我也会去进行修改
class Solution {
public void solve(char[][] board) {
if(board==null||board.length==0)
return ;
int row = board.length;
int col = board[0].length;
for(int i=0;i<row;i++){
dfs(board,i,0,row,col);
dfs(board,i,col-1,row,col);
}
for(int j=0;j<col;j++){
dfs(board,0,j,row,col);
dfs(board,row-1,j,row,col);
}
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(board[i][j]=='O') board[i][j]='X';
if(board[i][j]=='*') board[i][j]='O';
}
}
return ;
}
private void dfs(char[][] board,int i,int j,int row,int col){
if(i<0||j<0||i>row-1||j>col-1||board[i][j]!='O') return ;
board[i][j]='*';
dfs(board,i-1,j,row,col);
dfs(board,i+1,j,row,col);
dfs(board,i,j-1,row,col);
dfs(board,i,j+1,row,col);
return ;
}
}
最后的结果：
执行用时 : 3 ms, 在Surrounded Regions的Java提交中击败了100.00% 的用户
