法1：DFS
典型题目，牢记方法！
class Solution {
public void solve(char[][] board) {
int m = board.length, n = board[0].length;
if (m == 0 || n == 0) {
return;
}
boolean[][] visitedO = new boolean[m][n]; // 没有被围绕的'O'位置记录
for (int i = 0; i < n; ++i) {
// 首行
dfs(board, visitedO, 0, i, m, n);
}
for (int i = 0; i < n; ++i) {
// 末行
dfs(board, visitedO, m - 1, i, m, n);
}
for (int i = 0; i < m; ++i) {
// 首列
dfs(board, visitedO, i, 0, m, n);
}
for (int i = 0; i < m; ++i) {
// 末列
dfs(board, visitedO, i, n - 1, m, n);
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'O' && !visitedO[i][j]) {
board[i][j] = 'X';
}
}
}
}
public void dfs(char[][] board, boolean[][] visitedO, int i, int j, int m, int n) {
if (i >= 0 && i < m
&& j >= 0 && j < n
&& board[i][j] == 'O'
&& !visitedO[i][j]) {
visitedO[i][j] = true;
dfs(board, visitedO, i - 1, j, m, n);
dfs(board, visitedO, i + 1, j, m, n);
dfs(board, visitedO, i, j - 1, m, n);
dfs(board, visitedO, i, j + 1, m, n);
}
}
}
