529.md

529. Minesweeper

Implement a magic directory with buildDict, and search methods.

For the method buildDict, you'll be given a list of non-repetitive words to build a dictionary.

For the method search, you'll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.

Example 1:
Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False
Note:
You may assume that all the inputs are consist of lowercase letters a-z.
For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
Please remember to RESET your class variables declared in class MagicDictionary, as static/class variables are persisted across multiple test cases. Please see here for more details.

my thoughts:

1. depth first search

my solution:

**********399ms
class Solution(object):
    def updateBoard(self, board, click):
        """
        :type board: List[List[str]]
        :type click: List[int]
        :rtype: List[List[str]]
        """
        
        if board[click[0]][click[1]] == 'M':
            board[click[0]][click[1]] = 'X'
            return board
        
        n_coor = []
        
        for x in (click[0]-1, click[0], click[0]+1):
            for y in (click[1]-1, click[1], click[1]+1):
                if x>=0 and x<len(board) and y>=0 and y<len(board[0]) and (board[x][y] == 'M' or board[x][y] == 'E'):
                    if x == click[0] and y == click[1]:
                        continue
                    n_coor.append([x, y])
        
        if not n_coor:
            board[click[0]][click[1]] = 'B'
            return board
            
        neighbours = []
        for coor in n_coor:
            neighbours.append(board[coor[0]][coor[1]])
        
        foundMine = 0
        for position in neighbours:
            if position == 'M':
                foundMine += 1
                
        if foundMine != 0:
            board[click[0]][click[1]] = str(foundMine)
            return board
        else:
            board[click[0]][click[1]] = 'B'
            for coor in n_coor:
                board = self.updateBoard(board, coor)
            return board
        
        

my comments:

be more careful with the edge cases, as we are calling recursion, the click could be on a '1' or '3' which is precalculated. we want to just return the board to save some time.

from other ppl's solution:

1. remeber what has been visited, 279ms:
class Solution(object):
    def updateBoard(self, board, click):
        """
        :type board: List[List[str]]
        :type click: List[int]
        :rtype: List[List[str]]
        """
        if not board:
            return board
        m, n = len(board), len(board[0])
        frontier = [tuple(click)]
        visited = set()
        directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        while frontier:
            x, y = frontier.pop(0)
            if (x, y) in visited:
                continue
            visited.add((x, y))
            if board[x][y] == 'M':
                board[x][y] = 'X'
                return board
            count = 0
            neighbors = []
            for dx, dy in directions:
                r, c = x+dx, y+dy
                if 0<=r<m and 0<=c<n:
                    neighbors.append((r, c))
                    if board[r][c] == 'M':
                        count += 1
            if count == 0:
                board[x][y] = 'B'
                frontier += neighbors
            else:
                board[x][y] = str(count)
        return board