LeetCode 529 Minesweeper

LeetCode

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

You are given an m x n char matrix board representing the game board where:

'M' represents an unrevealed mine, 'E' represents an unrevealed empty square,
'B' represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals), digit ('1' to '8') represents how many mines are adjacent to this revealed square, and
'X' represents a revealed mine.

You are also given an integer array click where click = [clickr, clickc] represents the next click position among all the unrevealed squares ('M' or 'E').

Return the board after revealing this position according to the following rules:

1. If a mine 'M' is revealed, then the game is over. You should change it to 'X'.
2. If an empty square 'E' with no adjacent mines is revealed, then change it to a revealed blank 'B' and all of its adjacent unrevealed squares should be revealed recursively.
3. 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.
4. Return the board when no more squares will be revealed.

Example 1:

Input: board = [[“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”]]

Example 2:

Input: board = [[“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”]]

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 <= clickr < m 0 <= clickc < n
* board[clickr][clickc] is either 'M' or 'E'.

题目大意：

给定扫雷版上的某一个状态，计算扫雷版上的下一个状态

解题思路：

N/A

解题步骤：

N/A

注意事项：

三种情况： 1. 踩雷，只需更改此格。 2. 踩到数字格也就是雷相邻的格，计算此格的临近雷数，更改此格。 3. 从此格开始BFS访问全版，节点出列后如果是数字格不加入到queue中，否则继续BFS访问，更改此格。
x, y = node[0] + _dx, node[1] + _dy用node[0], node[1]不要用i, j

Python代码：

def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:

	if board[click[0]][click[1]] == 'M':
		board[click[0]][click[1]] = 'X'
		return board
	else:
		mine_num = self.get_neighboring_mine_num(board, click[0], click[1])
		if mine_num > 0:
			board[click[0]][click[1]] = str(mine_num)
			return board
		else:
			return self.bfs(board, click[0], click[1])

def bfs(self, board, i, j):
	queue = collections.deque([(i, j)])
	visited = set([(i, j)])
	while queue:
		node = queue.popleft()
		mine_num = self.get_neighboring_mine_num(board, node[0], node[1])
		if mine_num > 0:
			board[node[0]][node[1]] = str(mine_num)
			continue
		else:
			board[node[0]][node[1]] = 'B'
		for _dx, _dy in OFFSETS:
			x, y = node[0] + _dx, node[1] + _dy # remember not to use i, j
			if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or (x, y) in visited:
				continue
			queue.append((x, y))
			visited.add((x, y))
	return board

def get_neighboring_mine_num(self, board, i, j):
	num = 0
	for _dx, _dy in OFFSETS:
		x, y = i + _dx, j + _dy
		if 0 <= x < len(board) and 0 <= y < len(board[0]) and board[x][y] == 'M':
			num += 1
	return num

算法分析：

时间复杂度为O(n²)，空间复杂度O(n²)