LeetCode link

first thought

  • the regions which is not surrounded by X is must be started from one side
  • mark all the ‘O’ that stretched from sides with BFS
  • the other ‘O’ is the surrounded ‘O’

solution

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 {
    public void solve(char[][] board) {
        if (board == null) {
            return;
        }
        Queue<Position> queue = new LinkedList<>();
        int row = board.length;
        if (row < 3) {
            return;
        }
        int col = board[0].length;
        if (col < 3) {
            return;
        }
        for (int x = 0; x < row; x++) {
            this.helper(board, queue, x, 0);
        }
        for (int x = 0; x < row; x++) {
            this.helper(board, queue, x, col - 1);
        }
        for (int y = 0; y < col; y++) {
            this.helper(board, queue, 0, y);
        }
        for (int y = 0; y < col; y++) {
            this.helper(board, queue, row - 1, y);
        }
        for (int x = 0; x < row; x++) {
            for (int y = 0; y < col; y++) {
                if (board[x][y] == '.') {
                    board[x][y] = 'O';
                } else {
                    board[x][y] = 'X';
                }
            }
        }
    }
    private void helper(char[][] board, Queue<Position> queue, int x, int y) {
        int row = board.length;
        int col = board[0].length;
        int[] dirX = {-1, 0, 1, 0};
        int[] dirY = {0, 1, 0, -1};
        if (board[x][y] == 'O') {
            queue.add(new Position(x, y));
            while (!queue.isEmpty()) {
                Position pos = queue.poll();
                board[pos.x][pos.y] = '.';
                for (int d = 0; d < 4; d++) {
                    int newX = pos.x + dirX[d];
                    int newY = pos.y + dirY[d];
                    if (newX >= 0 && newX < row && newY >= 0 && newY < col && board[newX][newY] == 'O') {
                        queue.add(new Position(newX, newY));
                    }
                }
            }
        }
    }
}
class Position {
    int x;
    int y;
    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

problem

TLE, from 56/60.

reason

  • maybe there’s lots of duplicated iterations.
  • have seen the answer, maybe is the class Position took much more time, can solve this by changing the data from 2d into 1d. save the object save-read cost.

modification

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
class Solution {
    public void solve(char[][] board) {
        if (board == null) {
            return;
        }
        Queue<Integer> queue = new LinkedList<>();
        int row = board.length;
        if (row < 3) {
            return;
        }
        int col = board[0].length;
        if (col < 3) {
            return;
        }
        for (int x = 0; x < row; x++) {
            this.helper(board, queue, x, 0);
        }
        for (int x = 0; x < row; x++) {
            this.helper(board, queue, x, col - 1);
        }
        for (int y = 0; y < col; y++) {
            this.helper(board, queue, 0, y);
        }
        for (int y = 0; y < col; y++) {
            this.helper(board, queue, row - 1, y);
        }
        for (int x = 0; x < row; x++) {
            for (int y = 0; y < col; y++) {
                if (board[x][y] == '.') {
                    board[x][y] = 'O';
                } else {
                    board[x][y] = 'X';
                }
            }
        }
    }
    private void helper(char[][] board, Queue<Integer> queue, int x, int y) {
        int row = board.length;
        int col = board[0].length;
        int[] dirX = {-1, 0, 1, 0};
        int[] dirY = {0, 1, 0, -1};
        if (board[x][y] == 'O') {
            queue.add(x * col + y);
            while (!queue.isEmpty()) {
                Integer pos = queue.poll();
                int posX = pos / col;
                int posY = pos % col;
                board[posX][posY] = '.';
                for (int d = 0; d < 4; d++) {
                    int newX = posX + dirX[d];
                    int newY = posY + dirY[d];
                    if (newX >= 0 && newX < row && newY >= 0 && newY < col && board[newX][newY] == 'O') {
                        queue.add(newX * col + newY);
                    }
                }
            }
        }
    }
}

problem

still TLE…

reason

maybe there’s two more iterating in checking the sides? But I think there’s no difference, just try it.

modification

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
class Solution {
    public void solve(char[][] board) {
        if (board == null) {
            return;
        }
        Queue<Integer> queue = new LinkedList<>();
        int row = board.length;
        if (row < 3) {
            return;
        }
        int col = board[0].length;
        if (col < 3) {
            return;
        }
        for (int x = 0; x < row; x++) {
            this.helper(board, queue, x, 0);
            this.helper(board, queue, x, col - 1);
        }
        for (int y = 0; y < col; y++) {
            this.helper(board, queue, 0, y);
            this.helper(board, queue, row - 1, y);
        }
        for (int x = 0; x < row; x++) {
            for (int y = 0; y < col; y++) {
                if (board[x][y] == '.') {
                    board[x][y] = 'O';
                } else {
                    board[x][y] = 'X';
                }
            }
        }
    }
    private void helper(char[][] board, Queue<Integer> queue, int x, int y) {
        int row = board.length;
        int col = board[0].length;
        int[] dirX = {-1, 0, 1, 0};
        int[] dirY = {0, 1, 0, -1};
        if (board[x][y] == 'O') {
            queue.add(x * col + y);
            while (!queue.isEmpty()) {
                Integer pos = queue.poll();
                int posX = pos / col;
                int posY = pos % col;
                board[posX][posY] = '.';
                for (int d = 0; d < 4; d++) {
                    int newX = posX + dirX[d];
                    int newY = posY + dirY[d];
                    if (newX >= 0 && newX < row && newY >= 0 && newY < col && board[newX][newY] == 'O') {
                        queue.add(newX * col + newY);
                    }
                }
            }
        }
    }
}

problem

still TLE… And this time fail at case 54… worse solution…

reason

after have tried lots of modifications, it turns out the position of the code setting the board to ‘.’ does matter. move it from just after the poll operation to in the add queue operation can pass the problem. But I don’t know why. I think they’re the same… I’ll update when I make it clear.

modification

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
class Solution {
    public void solve(char[][] board) {
        if (board == null) {
            return;
        }
        int row = board.length;
        if (row < 3) {
            return;
        }
        int col = board[0].length;
        if (col < 3) {
            return;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int x = 0; x < row; x++) {
            this.helper(board, queue, x, 0);
            this.helper(board, queue, x, col - 1);
        }
        for (int y = 0; y < col; y++) {
            this.helper(board, queue, 0, y);
            this.helper(board, queue, row - 1, y);
        }
        for (int x = 0; x < row; x++) {
            for (int y = 0; y < col; y++) {
                if (board[x][y] == '.') {
                    board[x][y] = 'O';
                } else {
                    board[x][y] = 'X';
                }
            }
        }
    }
    private void helper(char[][] board, Queue<Integer> queue, int x, int y) {
        if (board[x][y] == 'O') {
            int row = board.length;
            int col = board[0].length;
            int[] dirX = {-1, 0, 1, 0};
            int[] dirY = {0, 1, 0, -1};
            board[x][y] = '.';
            queue.add(x * col + y);
            while (!queue.isEmpty()) {
                Integer pos = queue.poll();
                int posX = pos / col;
                int posY = pos % col;
                for (int d = 0; d < 4; d++) {
                    int newX = posX + dirX[d];
                    int newY = posY + dirY[d];
                    if (newX >= 0 && newX < row && newY >= 0 && newY < col && board[newX][newY] == 'O') {
                        board[newX][newY] = '.';
                        queue.add(newX * col + newY);
                    }
                }
            }
        }
    }
}

reason

Finally figure out the reason:

X O O
X O A
X X X

in the situations like above, the point A will be added to the queue twice.so the time cost will grow too much.