529. Minesweeper #

Problem #

Let’s play the minesweeper game ( Wikipedia, online game)!

You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine.

Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:

If a mine (‘M’) is revealed, then the game is over - change it to ‘X’.
If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively.
If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.
Return the board when no more squares will be revealed.

Example 1:

Input: 

[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:

Example 2:

Input: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:

Note:

The range of the input matrix’s height and width is [1,50].
The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.
The input board won’t be a stage when game is over (some mines have been revealed).
For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

Problem Summary #

Given a 2D character matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square with no adjacent (up, down, left, right, and all 4 diagonals) mines, a digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and ‘X’ represents a revealed mine. Now given the next click position (row and column indices) among all unrevealed squares (‘M’ or ‘E’), return the corresponding board after the position is clicked according to the following rules:

If a mine (‘M’) is revealed, the game is over - change it to ‘X’.
If an empty square (‘E’) with no adjacent mines is revealed, change it to (‘B’), and all adjacent unrevealed squares should be revealed recursively.
If an empty square (‘E’) with at least one adjacent mine is revealed, change it to a digit (‘1’ to ‘8’), representing the number of adjacent mines.
If no more squares can be revealed in this click, return the board.

Note:

The range of the input matrix’s width and height is [1,50].
The click position can only be an unrevealed square (‘M’ or ‘E’), which also means the board contains at least one clickable square.
The input board will not be in a game-over state (i.e., some mines have already been revealed).
For simplicity, rules not mentioned can be ignored in this problem. For example, when the game is over, you do not need to reveal all mines; consider all cases where you might win the game or flag squares.

Solution Approach #

Given a minesweeper map and the clicked coordinates, M represents a mine, E represents an empty square that has not been clicked, B represents an empty square that has been clicked, 1-8 represents the number of mines among the 8 surrounding squares, and X represents clicking on a mine. The question asks to output the updated map after one click.
DPS and BFS can both solve the problem. First preprocess the map according to the original map and record the final state of the map: 0 represents a blank square, 1-8 represents the number of mines, and -1 represents a mine. Then use DFS to traverse this processed map and output the final map.

Code #

func updateBoard(board [][]byte, click []int) [][]byte {
	if board[click[0]][click[1]] == 'M' {
		board[click[0]][click[1]] = 'X'
		return board
	}
	dfs(board, click[0], click[1])
	return board
}

func dfs(board [][]byte, x, y int) {
	cnt := 0
	for i := 0; i < 8; i++ {
		nx, ny := x+dir8[i][0], y+dir8[i][1]
		if isInBoard(board, nx, ny) && board[nx][ny] == 'M' {
			cnt++

		}
	}
	if cnt > 0 {
		board[x][y] = byte(cnt + '0')
		return
	}
	board[x][y] = 'B'
	for i := 0; i < 8; i++ {
		nx, ny := x+dir8[i][0], y+dir8[i][1]
		if isInBoard(board, nx, ny) && board[nx][ny] != 'B' {
			dfs(board, nx, ny)
		}
	}
}

func isInBoard(board [][]byte, x, y int) bool {
	return x >= 0 && x < len(board) && y >= 0 && y < len(board[0])
}