//DFS solution: scan for adjacent mines, if not, then call recursive function on 8 adjacent square
//Time: O(m * n), 4ms
//Space: O(m + n)
class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        if(board[click[0]][click[1]] == 'M') {
            board[click[0]][click[1]] = 'X';
            return board;
        }
        //The click position is an empty place
        DFS(board, click[0], click[1]);
        return board;
    }

    private void DFS(char[][] board, int r, int c) {
        //Base case: out of range or visited
        if(r < 0 || r >= board.length || c < 0 || c >= board[0].length || (board[r][c] != 'E' && board[r][c] != 'M')) {
            return;
        }
        int ans = 0;
        int[][] ardArr = new int[][]{{1, 1}, {1, 0}, {1, -1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};
        for(int[] ard : ardArr) {
            if(r + ard[0] >= 0 && r + ard[0] < board.length &&
               c + ard[1] >= 0 && c + ard[1] < board[0].length &&
               board[r + ard[0]][c + ard[1]] == 'M') {
                ans++;
            }
        }
        if(ans == 0) {
            board[r][c] = 'B';
            for(int[] ard : ardArr) {
                DFS(board, r + ard[0], c + ard[1]);
            }
        } else {
            board[r][c] = (char)('0' + ans);
        }
    }
}