Minesweeper - Leetcode Solution

The Minesweeper problem on LeetCode is a classic problem that involves using concepts of graph and BFS traversal. In this problem, we are given a 2D grid representing a Minesweeper game. Our goal is to uncover all the mines present in the grid, given that the mines are represented by 'M' and all the empty cells are represented by 'E'. Initially, all the cells in the grid are covered, and we start by clicking on a cell.

If the clicked cell is empty, then all its adjacent cells are also uncovered recursively, until we reach the cells that are adjacent to mine cells. If the clicked cell is a mine, the game is over, and all the mine cells are uncovered.

We are supposed to implement a function 'updateBoard(board: List[List[str]], click: List[int]) -> List[List[str]]' that takes in a 2D grid, 'board' and the coordinates of the cell clicked as a list of two integers, 'click'. The function returns a modified 'board' that includes the newly uncovered cells.

Here's the detailed solution to the Minesweeper problem on LeetCode.

Approach:

1. Create a queue and add the cell clicked to the queue.
2. While the queue is not empty, dequeue a cell.
3. If the dequeued cell is a mine, mark it as 'X', and the game is over.
4. If the dequeued cell is empty, uncover it by marking it as 'B'.
5. Count the number of mines present in its adjacent cells.
6. If any adjacent cell has a mine, mark the current cell with the count of mines.
7. If the adjacent cell is empty and unexplored, add it to the queue.

Implementation:

from typing import List

def updateBoard(board: List[List[str]], click: List[int]) -> List[List[str]]:
    m, n = len(board), len(board[0])
    row, col = click[0], click[1]
    if board[row][col] == 'M':
        board[row][col] = 'X'
        return board
    
    q = [(row, col)]
    while q:
        x, y = q.pop(0)
        if board[x][y] == 'E':
            count = 0
            directions = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'M':
                    count += 1
            if count > 0:
                board[x][y] = str(count)
            else:
                board[x][y] = 'B'
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'E':
                        q.append((nx, ny))
    return board

In the above implementation, we first find the dimensions of the given board, and the row and col coordinates of the clicked cell. We then create a queue and add the clicked cell to the queue.

Inside the while loop, we dequeue a cell and check if it is empty ('E') or a mine ('M'). If it is a mine, we mark it as 'X' and return the modified board.

If it is an empty cell, we count the number of mines present in its adjacent cells. We do this by iterating over all the adjacent cells using a list of tuples representing their relative positions. If we find a mine in any adjacent cell, we increment the count.

If the count is greater than 0, we mark the current cell with the count as a string.

If the count is 0, we mark the current cell as 'B', indicating that it is empty. We then add all the adjacent cells that are empty and have not been explored yet to the queue.

We continue this process until the queue is empty, and finally return the modified board.

Time Complexity: In the worst-case scenario, we might explore all the cells in the grid, so the time complexity of this algorithm is O(m*n).

Space Complexity: The maximum size of the queue could be O(mn), leading to space complexity as O(mn).

This is the solution to the Minesweeper problem on LeetCode.

1