Problem statement

https://leetcode.com/problems/minesweeper/

Solution

This problem is simpler that is sound for so long statement. All we need to do is to check if current click is Mine. If it is not, we need to traverse our board, using some bfs or dfs traversal. We evaluate number of neighbors, which are mines, and if we have more than zero, we just update board[x][y]. If we have zero mines, then we need to visit all neighbors.

Complexity

Time complexity is O(mn), space complexity is O(mn) potentially as well, because we can have snake-like coordinates of cells with zero mines neighbors.

Code

class Solution:
    def updateBoard(self, board, click):
        def dfs(x, y):
            if not 0 <= x < m or not 0 <= y < n: return
            
            if board[x][y] == "E":
                Nm = sum([board[x+dx][y+dy]=='M' for dx,dy in dirs if 0<=x+dx<m and 0<=y+dy<n])
                board[x][y] = str(Nm)
                
                if Nm == 0:
                    board[x][y] = "B"
                    for dx, dy in dirs: dfs(x+dx, y+dy)
        
        m, n = len(board), len(board[0])
        x, y = click[0], click[1]
        dirs = [[1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]]
        if board[x][y] == "M": 
            board[x][y] = "X"
        else:
            dfs(x, y)
        return board