题目描述（中等难度）
有一点点像围棋，把被x围起来的o变成x，边界的o一定不会被围起来。如果o和边界的o连通起来，那么这些o就都算作不被围起来，比如下边的例子。
X X X X X
O O O X X
X X X O X
X O X X X
上边的例子就只需要变化1个o.
解法一
把相邻的o看做是联通的图，然后从每一个o开始做DFS。
如果遍历完成后没有到达边界的o，我们就把当前o改成x。
如果遍历过程中达到了边界的o，直接结束DFS，当前的o就不用操作。
然后继续考虑下一个o，继续做一次DFS。
public class Surrounded_Regions {public void solve(char[][] board){if(board.length==0 || board[0].length==0) return;int m = board.length,n=board[0].length;// start from first and last column,turn 'o' to '*'for(int i = 0;i<m;i++){if(board[i][0]=='o')boundaryDFS(board,i,0);if(board[i][n-1]=='o')boundaryDFS(board,i,n-1);}//start from first and last row,turn 'o' to '*'for(int j=0;j<n;j++){if(board[0][j]=='o')boundaryDFS(board,0,j);if(board[m-1][j]=='o')boundaryDFS(board,m-1,j);}for(int i =0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j]=='o')board[i][j]='x';else if(board[i][j]=='*')board[i][j]='o';}}}private void boundaryDFS(char[][] board,int i,int j){if(i<0 ||j<0 || i>board.length-1 || j>board[0].length-1 || board[i][j]!='o')return;board[i][j]='*';boundaryDFS(board,i+1,j);boundaryDFS(board,i-1,j);boundaryDFS(board,i,j+1);boundaryDFS(board,i,j-1);}
}
参考文献
- https://leetcode.com/problems/surrounded-regions/discuss/41633/Java-DFS-%2B-boundary-cell-turning-solution-simple-and-clean-code-commented.