LeetCode : 130. Surrounded Regions

[congr]

https://leetcode.com/problems/surrounded-regions/

[congr]

class Solution {
    public void solve(char[][] board) {
        if (board.length == 0) return;
        int M = board.length, N = board[0].length;

        for (int i = 0; i < M; i++) {
            dfs(board, i, 0);
            dfs(board, i, N-1);
        }

        for (int j = 0; j < N; j++) {
            dfs(board, 0, j);
            dfs(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] == '*') board[i][j] = 'O'; // !!
            }
        }
    }

    int[] dx = {-1,0,1,0};
    int[] dy = {0,-1,0,1};
    void dfs(char[][] board, int y, int x) {
        if (board[y][x] != 'O') return;
        board[y][x] = '*';

        for (int d = 0; d < 4; d++) {
            int ny = y + dy[d], nx = x + dx[d];
            if (ny < 0 || nx < 0 || ny >= board.length || nx >= board[0].length) continue;
            if (board[ny][nx] == 'O') dfs(board, ny, nx);
        }
    }
}