130. Surrounded Regions

发表于 | 分类于

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,

1
2
3
4
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

1
2
3
4
X X X X
X X X X
X X X X
X O X X

解法1: DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
    int[][] ds = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return;
        }
        int row = board.length;
        int col = board[0].length;
        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][col - 1] == 'O') {
                dfs(board, i, col - 1);
            }
        }
        for (int j = 0; j < col; j++) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            if (board[row - 1][j] == 'O') {
                dfs(board, row - 1, j);
            }
        }
        // Need to convert all 'M' into 'O'
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'M') {
                    board[i][j] = 'O';
                }
            }
        }
    }
//     private void dfs(char[][] board, int i, int j) {
//         board[i][j] = 'M';
//         for (int[] d : ds) {
//             int x = i + d[0];
//             int y = j + d[1];
//             if (x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] == 'O') {
//                 dfs(board, x, y);
//             }
//         }
//     }
    private void dfs(char[][] board, int i, int j) {
        if (i < 0 || i > board.length - 1 || j <0 || j > board[0].length - 1)
            return;
        if (board[i][j] == 'O')
            board[i][j] = 'M';
        if (i > 1 && board[i-1][j] == 'O')
            dfs(board, i-1, j);
        if (i < board.length - 2 && board[i+1][j] == 'O')
            dfs(board, i+1, j);
        if (j > 1 && board[i][j-1] == 'O')
            dfs(board, i, j-1);
        if (j < board[i].length - 2 && board[i][j+1] == 'O' )
            dfs(board, i, j+1);
    }
}

解法2: BFS

这题DFS的解法非常容易出现stack overflow。 主要的原因是在判断对那个方向进行DFS的时候如果不避免边界上的点的话就会overflow，所以我们要跳过那些边界的点而只看纵深的点。如果用BFS的话情况会好不少，不过要写对也不容易。基本思路也是对于边界上的O点，使用BFS把所有相通的都标注一下。
不过在进行BFS的时候，每一个新的点push进queue的时候，立即把他标注成M，这样可以减少push的点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
    int[][] directions = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return;
        }
        int m = board.length;
        int n = board[0].length;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                bfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                bfs(board, i, n - 1);
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                bfs(board, 0, j);
            }
            if (board[m - 1][j] == 'O') {
                bfs(board, m - 1, j);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                } else if (board[i][j] == 'M') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    private void bfs(char[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i * n + j);
        board[i][j] = 'M';
        while (!queue.isEmpty()) {
            int temp = queue.poll();
            int row = temp / n;
            int col = temp % n;
            for (int[] dir : directions) {
                int x = row + dir[0];
                int y = col + dir[1];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
                    queue.offer(x * n + y);
                    board[x][y] = 'M';
                }
            }
        }
    }
}