repl.it
@shachopin/

Surrounded Regions

Java

No description

fork
loading
Files
  • Main.java
  • jdt.ls-java-project
Main.java
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
class Main {
  public static void main(String[] args) {
    System.out.println("Hello world!");
  }
}


public class Solution {
    /*
     * @param board: board a 2D board containing 'X' and 'O'
     * @return: nothing
     */
    //类似number of islands
    //BFS six questions answers
    //二维
    //flood fill
    //单源
    //不在乎target, 因为不是shortest path问题
    //重用题目给的2D array
    //二重循环
    int[] dx = new int[]{0, -1, 1, 0};
    int[] dy = new int[]{1, 0, 0, -1};
    public void surroundedRegions(char[][] board) {
        // write your code here
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        
        int rows = board.length;
        int cols = board[0].length;
        
        for (int i = 0; i < rows; i++) {
            // if (board[i][0] == 'X') {
            //     continue;
            // }
            bfs(board, i, 0);
            
            // if (board[i][cols - 1] == 'X') {
            //     continue;
            // }
            bfs(board, i, cols - 1);
        }
        
        for (int i = 0; i < cols; i++) {
            // if (board[0][i] == 'X') {
            //     continue;
            // }
            bfs(board, 0, i);
            
            // if (board[rows - 1][i] == 'X') {
            //     continue;
            // }
            bfs(board, rows - 1, i);
        }
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'W') {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X'; 
                }
            }
        }
    }
    
    
    private void bfs(char[][] board, int x, int y) {
        if (board[x][y] == 'X') {
            return;
        }
        //is 'O'
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y));
        board[x][y] = 'W';
        while (!queue.isEmpty()) {
            Point curPoint = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = curPoint.x + dx[i];
                int ny = curPoint.y + dy[i];
                if (nx < 0 || nx >= board.length || ny < 0 || ny >= board[0].length) { 
                    continue;
                }
                if (board[nx][ny] != 'O') {
                    continue;
                }
                
                queue.offer(new Point(nx, ny));
                board[nx][ny] = 'W';
            }
        }
        
    }
}

class Point {
    int x;
    int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}