Reveal a Minesweeper Region with Adjacent-Mine Counts

Question

This question asks the candidate to implement a solution for revealing a Minesweeper game board, specifically calculating the number of adjacent mines for each cell in the board.

Codemia · Accepted Answer

To solve the Minesweeper problem, we need to create a function that takes a board as input and outputs a new board with the counts of adjacent mines for each cell. The board consists of cells that can either be a mine (-1), an unrevealed empty cell (0), or a revealed empty cell (-2). Our goal is to calculate the number of mines surrounding each unrevealed empty cell.

We will use a depth-first search (DFS) approach to explore the board. The algorithm will iterate through each cell, and for each unrevealed empty cell, it will check its adjacent cells to count the number of mines. If a cell has no adjacent mines, we will recursively reveal its neighbors until we hit cells that have adjacent mines.

1. **Iterate through the board**: Loop through each cell in the grid.  
2. **Check cell status**: If the cell is a mine, we skip it. If it is an unrevealed empty cell, we proceed to count adjacent mines.  
3. **Count adjacent mines**: For each unrevealed empty cell, check all eight possible directions (up, down, left, right, and the four diagonals) to count how many mines are adjacent.  
4. **DFS for empty cells**: If there are no adjacent mines, we perform DFS on the cell to reveal its neighbors.

Here is a Python implementation of the solution:
```python
def reveal_board(board):
    rows, cols = len(board), len(board[0])
    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

def count_mines(r, c):
        count = 0
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == -1:
                count += 1
        return count

for r in range(rows):
        for c in range(cols):
            if board[r][c] == 0:
                mine_count = count_mines(r, c)
                board[r][c] = mine_count
    return board
```
This code iterates through the board and counts adjacent mines for each unrevealed empty cell.

This approach has a time complexity of O(n*m) where n is the number of rows and m is the number of columns in the board. The space complexity is O(n*m) as well due to the recursion stack in DFS. For larger boards, we may consider iterative approaches to avoid stack overflow and optimize memory usage. Additionally, we can implement memoization to cache results of previously calculated cells to improve performance.

Reveal a Minesweeper Region with Adjacent-Mine Counts

Nuro

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Nuro Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string