Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
题意：给出一个二维矩阵，中间只有X和O，要求把被X包围的O全部变为X，没被包围的O保持不变。
思路：
先把所有没有被包围的O标识出来，然后把剩下的O转为X。
没有被包围的O肯定都要连接到矩形边缘，所以遍历矩形边缘，遇到了O，就用深度搜索把所有与这个O相连的O都标识出来。
public int[] dx = {1, 0, -1, 0};
public int[] dy = {0, 1, 0, -1};
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
int xlen = board.length;
int ylen = board[0].length;
for (int x = 0; x < xlen; x++) {
for (int y = 0; y < ylen; y++) {
if ((x == 0 || x == xlen - 1 || y == 0 || y == ylen - 1) && board[x][y] == 'O') {
dfs(x, y, board);
}
}
}
for (int x = 0; x < xlen; x++) {
for (int y = 0; y < ylen; y++) {
if (board[x][y] == 'O') {
board[x][y] = 'X';
} else if (board[x][y] == '#') {
board[x][y] = 'O';
}
}
}
}
private void dfs(int x, int y, char[][] board) {
board[x][y] = '#';
for (int i = 0; i < 4; i++) {
int tx = x + dx[i];
int ty = y + dy[i];
if (tx < 0 || tx >= board.length || ty < 0 || ty >= board[0].length || board[tx][ty] != 'O') {
continue;
}
dfs(tx, ty, board);
}
}