# LEETCODE 130. Surrounded Regions 解题思路分析

```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```

```public void solve(char[][] board) {
if(board.length==0) return;
int row=board.length, col=board[0].length;
// 以第一行与最后一行上的所有'O'为起点做dfs
// 将所有与他们连通的'O'置换为'A'
for(int c=0;c<col;c++){
if(board[0][c]=='O'){
dfs(board, 0, c);
}
if(board[row-1][c]=='O'){
dfs(board, row-1, c);
}
}
// 以第一列与最后一列上的所有'O'为起点做dfs
// 将所有与他们连通的'O'置换为'A'
for(int r=0;r<row;r++){
if(board[r][0]=='O'){
dfs(board, r, 0);
}
if(board[r][col-1]=='O'){
dfs(board, r, col-1);
}
}
// 遍历矩阵每一个点，将'O'替换为'X'，将'A'替换为'O'
for(int r=0;r<row;r++){
for(int c=0;c<col;c++){
if(board[r][c]=='O'){
board[r][c]='X';
}
if(board[r][c]=='A'){
board[r][c]='O';
}
}
}
}
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
void dfs(char[][] board,int r, int c){
board[r][c]='A';
for(int[] d : dirs){
int row=d[0]+r,col=d[1]+c;
if(row>=0&&row<board.length&&col>=0&&col<board[0].length
&&board[row][col]=='O'){
dfs(board, row, col);
}
}
}```

Runtime: 1 ms, faster than 99.39% of Java online submissions for Surrounded Regions.

Memory Usage: 41.8 MB, less than 40.49% of Java online submissions for Surrounded Regions.