130. Surrounded Regions - Medium

前往題目

想法

• 用DFS看每個島嶼在哪，然後翻轉，但是要注意外圈的O會使得比鄰的O不能被反轉，這部分不知道怎麼做，得另外再搜尋哪些有比鄰

思路

1. 用BFS從border開始更好理解
2. 從外圈開始遇到O就BFS搜尋比鄰它的O，感染的概念，一個接著一個感染，並先標記為#
3. 最後搜尋完了之後再疊代整個board，遇到O就是沒有比鄰的，直接翻轉為X，遇到#就是比鄰的O，翻轉回O

Code

文字解析

class Solution {
    private int ROWS;
    private int COLS;
    private int[][] dir = new int[][]{
            {1, 0}, 
            {-1, 0}, 
            {0, 1}, 
            {0, -1}
        };

    public void solve(char[][] board) {
        ROWS = board.length;
        COLS = board[0].length;

        // Check border
        // 1 col. and last col.
        for (int i = 0; i < ROWS; ++i) {
            if (board[i][0] == 'O') bfs(board, i, 0);
            if (board[i][COLS - 1] == 'O') bfs(board, i, COLS - 1);
        }

        // Check 1 row and last row
        for (int j = 0; j < COLS; ++j) {
            if (board[0][j] == 'O') bfs(board, 0, j);
            if (board[ROWS - 1][j] == 'O') bfs(board, ROWS - 1, j);
        }

        // Flip
        for (int row = 0; row < ROWS; ++row) {
            for (int col = 0; col < COLS; ++col) {
                if (board[row][col] == 'O') {
                    board[row][col] = 'X';
                } else if (board[row][col] == '#') {
                    board[row][col] = 'O';
                }
            }
        }
    }

    private void bfs(char[][] board, int r, int c) {
        Queue<int[]> q = new LinkedList<>();
        // Add the starting position
        q.offer(new int[]{r, c});
        // Flip to # to mark 'O'
        board[r][c] = '#';

        while (!q.isEmpty()) {
            int row = q.peek()[0];
            int col = q.peek()[1];
            q.poll();

            for (int i = 0; i < 4; ++i) {
                int adjX = row + dir[i][0];
                int adjY = col + dir[i][1];

                // Check out of bound
                if (adjX < 0 || adjX >= ROWS || adjY < 0 || adjY >= COLS) 
                    continue;

                // Only care 'O'
                if (board[adjX][adjY] != 'O')
                    continue;

                // Mark as '#'
                board[adjX][adjY] = '#';

                // Add to queue
                q.offer(new int[]{adjX, adjY});
            }
        }
    }

}