Minesweeper (Matrix)

Given a Minesweeper board click, reveal cells according to game rules. M=mine, E=empty, B=blank revealed, X=hit mine.

Example 1

Reveal from click position using BFS, expanding blank cells.

Solution Approach

BFS from click: if M mark X. Count adjacent mines. If 0 mark B and expand. If >0 mark as digit.

BFS queue from click.
If M: set X. Else count adjacent mines.
If count>0: set digit char.
If count==0: set B, add all E neighbors to queue.

Java

import java.util.*;

class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int r=click[0], c=click[1], m=board.length, n=board[0].length;
        if (board[r][c]=='M') { board[r][c]='X'; return board; }
        int[][] dirs={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        Queue<int[]> q=new LinkedList<>(); q.offer(click); board[r][c]='B';
        while (!q.isEmpty()){
            int[] cur=q.poll(); int mines=0; List<int[]> nb=new ArrayList<>();
            for (int[] d:dirs){int nr=cur[0]+d[0],nc=cur[1]+d[1];
                if(nr>=0&&nr<m&&nc>=0&&nc<n){if(board[nr][nc]=='M')mines++;else if(board[nr][nc]=='E')nb.add(new int[]{nr,nc});}}
            if (mines>0) board[cur[0]][cur[1]]=(char)('0'+mines);
            else for (int[] e:nb){board[e[0]][e[1]]='B';q.offer(e);}
        }
        return board;
    }
}

Time Complexity: O(M*N)
Space Complexity: O(M*N)