Show problems as
Classic problem #529MediumArrayDepth-First SearchBreadth-First SearchMatrix

Minesweeper

Real-world version: Test Pit on the Survey Grid
Tracked in this browser only
Read Minesweeper on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A construction site is surveyed square by square before anyone digs. board is the survey sheet, one character per square:

  • 'M' a buried shell that the survey has located.
  • 'E' earth nobody has opened up yet.
  • 'B' earth already opened up with no shell in any square touching it.
  • a digit '1' through '8', earth already opened up, the digit being how many of the squares touching it hold a shell.

Two squares touch when they share an edge or just a corner, so a square away from the border touches eight others.

The surveyor sinks one test pit at click = [click_r, click_c], and that square is always 'M' or 'E'. Work the sheet as follows:

  1. If the pit lands on 'M', the shell is struck: write 'X' on that square and the survey stops there.
  2. Otherwise the square is opened up. If any touching square holds a shell, write the digit counting them on the square and go no further from it.
  3. If no touching square holds a shell, write 'B' on the square and then open up every touching square that is still 'E' by these same rules, continuing outward from each square that turns out to be 'B'.

Squares that already carry 'B' or a digit when the pit is sunk are left exactly as they are, are never opened up again, and the opening up never spreads outward from them. Modify board in place and return it.

Examples

Example 1

Input
board = [["E", "E", "M", "E"], ["E", "E", "E", "E"], ["M", "E", "E", "E"], ["E", "E", "E", "E"]], click = [0, 0]
Output
[["B", "1", "M", "E"], ["1", "2", "E", "E"], ["M", "E", "E", "E"], ["E", "E", "E", "E"]]

No shell touches the pit square, so it becomes `"B"` and the survey opens up the three squares touching it. Each of those has a shell somewhere among the squares it touches, so each takes a digit and the survey goes no further.

Example 2

Input
board = [["E", "E", "E"], ["E", "M", "E"], ["E", "E", "E"]], click = [1, 1]
Output
[["E", "E", "E"], ["E", "X", "E"], ["E", "E", "E"]]

The pit lands straight on a located shell, so that square is marked struck and nothing else on the sheet changes.

Example 3

Input
board = [["E", "E", "E"], ["E", "M", "E"], ["E", "E", "E"]], click = [0, 0]
Output
[["1", "E", "E"], ["E", "M", "E"], ["E", "E", "E"]]

The corner square touches the shell in the middle, so it takes the digit for one shell and the rest of the sheet is left alone.

Example 4

Input
board = [["M", "M", "M"], ["M", "E", "M"], ["M", "M", "M"]], click = [1, 1]
Output
[["M", "M", "M"], ["M", "8", "M"], ["M", "M", "M"]]

The middle square is surrounded on all eight sides by located shells, so it takes the digit for eight.

Example 5

Input
board = [["E", "E", "E", "E"], ["E", "E", "E", "E"], ["E", "E", "E", "E"]], click = [1, 2]
Output
[["B", "B", "B", "B"], ["B", "B", "B", "B"], ["B", "B", "B", "B"]]

The sheet holds no shells at all, so the pit square becomes `"B"` and the opening up carries on until every square on the sheet is `"B"`.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 50
  • board[i][j] is either 'M', 'E', 'B', or a digit from '1' to '8'.
  • click.length == 2
  • 0 <= click_r < m
  • 0 <= click_c < n
  • board[click_r][click_c] is either 'M' or 'E'.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def update_board(board: list[list[str]], click: list[int]) -> list[list[str]]:
Java
public char[][] updateBoard(char[][] board, int[] click)

More on the same topics