LC 0529 [M] Minesweeper - ALawliet/algorithms GitHub Wiki
https://www.youtube.com/watch?v=lla6QlAF4HQ&ab_channel=babybear4812
this is how you do diags, see how the 2x loops add +2 for 2*2=4 diags
for r in range(x-1, x+2):
for c in range(y-1, y+2):
'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.
class Solution:
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
def getAdjacentMines(x, y):
numMines = 0
for r in range(x-1, x+2):
for c in range(y-1, y+2):
if 0 <= r < len(board) and 0 <= c < len(board[r]) and board[r][c] == 'M':
numMines += 1
return numMines
if not board:
return board
x, y = click
if board[x][y] == 'M':
board[x][y] = 'X'
else:
numMines = getAdjacentMines(x, y)
if numMines:
board[x][y] = str(numMines)
else:
board[x][y] = 'B'
for r in range(x-1, x+2):
for c in range(y-1, y+2):
if 0 <= r < len(board) and 0 <= c < len(board[r]) and board[r][c] != 'B':
self.updateBoard(board, [r, c])
return board
class Solution:
def updateBoard2(self, board, click):
"""
:type board: List[List[str]]
:type click: List[int]
:rtype: List[List[str]]
"""
if not board:
return []
m, n = len(board), len(board[0])
i, j = click[0], click[1]
# If a mine ('M') is revealed, then the game is over - change it to 'X'.
if board[i][j] == 'M':
board[i][j] = 'X'
return board
# run dfs to reveal the board
self.dfs(board, i, j)
return board
def dfs(self, board, i, j):
if board[i][j] != 'E':
return
m, n = len(board), len(board[0])
directions = [(-1,-1), (0,-1), (1,-1), (1,0), (1,1), (0,1), (-1,1), (-1,0)]
mine_count = 0
for d in directions:
ni, nj = i + d[0], j + d[1]
if 0 <= ni < m and 0 <= nj < n and board[ni][nj] == 'M':
mine_count += 1
if mine_count == 0:
board[i][j] = 'B'
else:
board[i][j] = str(mine_count)
return
for d in directions:
ni, nj = i + d[0], j + d[1]
if 0 <= ni < m and 0 <= nj < n:
self.dfs(board, ni, nj)