# Minesweeper

## Problem

Let's play the minesweeper game ([Wikipedia](https://en.wikipedia.org/wiki/Minesweeper_\(video_game\)), [online game](http://minesweeperonline.com/))!

You are given a 2D char matrix representing the game board. **'M'** represents an **unrevealed** mine, **'E'** represents an **unrevealed** empty square, **'B'** represents a **revealed** blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, **digit** ('1' to '8') represents how many mines are adjacent to this **revealed** square, and finally **'X'** represents a **revealed** mine.

Now given the next click position (row and column indices) 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 - change it to **'X'**.
2. If an empty square ('E') with **no adjacent mines** is revealed, then change it to 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.

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MRLeTBDzMpvgGghYqdk%2F-MRMxPqyGtcYMQnqB7EN%2FScreen%20Shot%202021-01-18%20at%205.05.04%20PM.png?alt=media\&token=7486483f-e5ef-4efa-bb87-a29cdd21e74c)

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MRLeTBDzMpvgGghYqdk%2F-MRMxYGxsy9MZeozfr8S%2FScreen%20Shot%202021-01-18%20at%205.05.42%20PM.png?alt=media\&token=93f54045-b131-4a60-aa8c-04081cd10ca7)

### Thought Process

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MRLeTBDzMpvgGghYqdk%2F-MRN3mBNPkCwsds8j7tx%2FIMG_534F097ECC60-1.jpeg?alt=media\&token=f2d13c5e-1608-4337-b09b-ababab6d693c)

* There's a BFS solution and DFS solution. I implemented both

## Solution 

```
from collections import deque

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        
        visited = set()
        q = deque()
        i, j = click[0], click[1]
        q.append([i,j])
        visited.add((i,j))
        
        directions = [[-1,0], [1,0], [0,-1], [0,1],[-1,-1], [-1,1], [1,-1], [1,1]]
        
        while q:
            coor = q.popleft()
            print(q)
            x, y = coor[0], coor[1]
            print(x,y)
        
            if board[x][y] == 'M':
                board[x][y] = 'X'
            
            else: #see how many bombs are around
                
                count = 0
                for d in directions:
                    newX, newY = x+d[0], y+d[1]
                  
                    
                    if newX < 0 or newX >= len(board) or newY < 0 or newY >= len(board[0]):
                        continue
                    elif board[newX][newY] == 'M' or board[newX][newY] == 'X' :
                        count+=1
                        
                if count != 0: #we don't want to do BFS if a bomb is near
                    board[x][y] = str(count)
                    
                else:
                    board[x][y] = 'B'
                    
                    for dd in directions:
                        newX, newY = x+dd[0], y+dd[1]
                        if newX < 0 or newX >= len(board) or newY < 0 or newY >= len(board[0]) or (newX, newY) in visited:
                            continue
                        
                        if board[newX][newY] == 'E':
                            q.append([newX, newY])
                            
                            visited.add((newX, newY))
            
        return board
                        
```

### DFS Solution

```
class Solution:
    def checkMines(self, x, y, board):
        numMines = 0
        for i in range(x-1,x+2):
            for j in range(y-1, y+2):
                if i >= 0 and i < len(board) and j >= 0 and j < len(board[i]) and board[i][j] == 'M':
                    numMines+=1
        return numMines
        
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        
        x, y = click[0], click[1]
        
        if board[x][y] == 'M':
            board[x][y] = 'X'
              
        else:
            mines = self.checkMines(x,y,board)
            if mines:
                board[x][y] = str(mines)
            else: #no mines adjacent
                board[x][y] = 'B'
                for i in range(x-1,x+2):
                    for j in range(y-1, y+2):
                        if i >= 0 and i < len(board) and j >= 0 and j < len(board[i]) and board[i][j] != 'B':
                            self.updateBoard(board, [i,j])
        return board
        
```

## Time Complexity

* **Time:** O(m\*n) for both BFS and DFS since we are traversing through the matrix

* **Space**: O(m\*n) for both BFS and DFS. With a queue we are storing every cell and with recusrion the call stack will be m\*n.&#x20;