Python Solution - DFS - Simple code - No hashtable Required


  • 2
    H
    import collections
    class Solution(object):
        def updateBoard(self, board, click):
            if not board:
                return
            m, n = len(board), len(board[0])
            queue = collections.deque()
            queue.append((click[0], click[1]))
            valid_neighbours = lambda (i, j): 0<=i<m and 0<=j<n
    
            while queue:
                x, y = queue.pop()
                if board[x][y] == 'M':
                    board[x][y] = 'X'
                else:
                    # Filter out the valid neighbours
                    neighbours = filter(valid_neighbours, [(x-1, y), (x+1, y), 
                        (x, y-1), (x, y+1), (x-1, y-1), (x+1, y-1), (x-1, y+1), (x+1, y+1)])
                    # Count the number of mines amongst the neighbours
                    mine_count = sum([board[i][j]=='M' for i, j in neighbours])
                    # If at least one neighbour is a potential mine, store the mine count.
                    if mine_count > 0:
                        board[x][y] = str(mine_count)
                    # If no neighbour is a mine, then add all unvisited neighbours
                    # to the queue for future processing
                    else:
                        board[x][y] = 'B'
                        queue.extend([(i, j) for (i, j) in neighbours if board[i][j]=='E'])
            return board
    

  • 0
    A

    @humachine Hi, Why is this a DFS and not a BFS?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.