‘X‘ and ‘O‘, capture all regions surrounded by ‘X‘.A region is captured by flipping all ‘O‘‘s into ‘X‘‘s in that surrounded region.
Example 1:
Input:
X X X X
X O O X
X X O X
X O X X
Output:
X X X X
X X X X
X X X X
X O X X
Example 2:
Input:
X X X X
X O O X
X O O X
X O X X
Output:
X X X X
X O O X
X O O X
X O X X
思路：可以使用BFS或DFS解题.
方法1:
在记录每个节点是否访问过的前提下, 依次从每个 ‘O‘ 开始BFS/DFS, 并且只访问未访问过的 ‘O‘.
如果从一个 ‘O‘ 可以访问到边界, 那么不做任何操作; 否则便将这个 ‘O‘ 可以访问到的所有的 ‘O‘ 替换为 ‘X‘.
方法2:
从每个边界的 ‘O‘ 开始遍历, 只访问 ‘O‘, 先都暂时设置为 ‘T‘ 或其他字符.
遍历结束之后, 将剩下的 ‘O‘ 替换为 ‘X‘ 然后再将 ‘T‘ 还原即可.
public class Solution {
public void surroundedRegions(char[][] board) {
// Write your code here
int n = board.length;
if (n == 0) {
return;
}
int m = board[0].length;
for (int i = 0; i < n; i++) {
bfs(board, i, 0);
bfs(board, i, m - 1);
}
for (int j = 0; j < m; j++) {
bfs(board, 0, j);
bfs(board, n - 1, j);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == ‘W‘) {
board[i][j] = ‘O‘;
} else {
board[i][j] = ‘X‘;
}
}
}
}
void bfs(char[][] board, int sx, int sy) {
if (board[sx][sy] != ‘O‘) {
return;
}
int n = board.length;
int m = board[0].length;
int[] dx = { 0, 1, 0, -1 };
int[] dy = { 1, 0, -1, 0 };
Queue<Integer> qx = new LinkedList<>();
Queue<Integer> qy = new LinkedList<>();
qx.offer(sx);
qy.offer(sy);
board[sx][sy] = ‘W‘; // ‘W‘ -> Water
while (!qx.isEmpty()) {
int cx = qx.poll();
int cy = qy.poll();
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (0 <= nx && nx < n && 0 <= ny && ny < m && board[nx][ny] == ‘O‘) {
board[nx][ny] = ‘W‘; // ‘W‘ -> Water
qx.offer(nx);
qy.offer(ny);
}
}
}
}
}
原文：https://www.cnblogs.com/FLAGyuri/p/12078591.html