这道题和这两道题是一样的思路:
200. Number of Islands
286. Walls and Gates
Time = O(mn), space = O(mn) (递归栈的大小)
class Solution {
private int[][] dirs = {`{-1, 0}, {1, 0}, {0, -1}, {0, 1}`};
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
for (int i = 0; i < board.length; i++) {
if (board[i][0] == 'O') {
dfsHelper(i, 0, board);
}
if (board[i][board[0].length - 1] == 'O') {
dfsHelper(i, board[0].length - 1, board);
}
}
for (int j = 0; j < board[0].length; j++) {
if (board[0][j] == 'O') {
dfsHelper(0, j, board);
}
if (board[board.length - 1][j] == 'O') {
dfsHelper(board.length - 1, j, board);
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == 'B') {
board[i][j] = 'O';
}
}
}
}
private void dfsHelper(int i, int j, char[][] board) {
if (i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1 || board[i][j] != 'O') { // 注意这里剪枝要剪掉X和B
return;
}
board[i][j] = 'B';
for (int[] dir : dirs) {
dfsHelper(i + dir[0], j + dir[1], board);
}
}
}
Time = O(mn), space = O(mn)(?) (Queue的大小)
class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
int[][] dirs = {`{-1, 0}, {1, 0}, {0, -1}, {0, 1}`};
Deque<int[]> queue = new ArrayDeque<>();
for (int i = 0; i < board.length; i++) {
if (board[i][0] == 'O') {
queue.offerLast(new int[]{i, 0});
}
if (board[i][board[0].length - 1] == 'O') {
queue.offerLast(new int[]{i, board[0].length - 1});
}
}
for (int j = 0; j < board[0].length; j++) {
if (board[0][j] == 'O') {
queue.offerLast(new int[]{0, j});
}
if (board[board.length - 1][j] == 'O') {
queue.offerLast(new int[]{board.length - 1, j});
}
}
while (!queue.isEmpty()) {
int[] cur = queue.pollFirst();
board[cur[0]][cur[1]] = 'B';
for (int[] dir : dirs) {
int x = cur[0] + dir[0];
int y = cur[1] + dir[1];
if (x < 0 || x > board.length - 1 || y < 0 || y > board[0].length - 1 || board[x][y] != 'O') {
continue;
}
queue.offerLast(new int[]{x, y});
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == 'B') {
board[i][j] = 'O';
}
}
}
}
}
TODO