Leetcode

Minesweeper

  • Time:O(mn)
  • Space:O(mn)

C++

class Solution {
 public:
  vector<vector<char>> updateBoard(vector<vector<char>>& board,
                                   vector<int>& click) {
    if (board[click[0]][click[1]] == 'M') {
      board[click[0]][click[1]] = 'X';
      return board;
    }

    dfs(board, click[0], click[1]);

    return board;
  }

 private:
  const vector<pair<int, int>> dirs{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
                                    {0, 1},   {1, -1}, {1, 0},  {1, 1}};

  void dfs(vector<vector<char>>& board, int i, int j) {
    if (i < 0 || i == board.size() || j < 0 || j == board[0].size())
      return;
    if (board[i][j] != 'E')
      return;

    const int minesCount = getMinesCount(board, i, j);
    board[i][j] = minesCount == 0 ? 'B' : '0' + minesCount;

    if (minesCount == 0)
      for (const auto& [dx, dy] : dirs)
        dfs(board, i + dx, j + dy);
  }

  int getMinesCount(const vector<vector<char>>& board, int i, int j) {
    int minesCount = 0;
    for (const auto& [dx, dy] : dirs) {
      const int x = i + dx;
      const int y = j + dy;
      if (x < 0 || x == board.size() || y < 0 || y == board[0].size())
        continue;
      if (board[x][y] == 'M')
        ++minesCount;
    }
    return minesCount;
  }
};

JAVA

class Solution {
  public char[][] updateBoard(char[][] board, int[] click) {
    if (board[click[0]][click[1]] == 'M') {
      board[click[0]][click[1]] = 'X';
      return board;
    }

    dfs(board, click[0], click[1]);

    return board;
  }

  private static final int[][] dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
                                       {0, 1},   {1, -1}, {1, 0},  {1, 1}};

  private void dfs(char[][] board, int i, int j) {
    if (i < 0 || i == board.length || j < 0 || j == board[0].length)
      return;
    if (board[i][j] != 'E')
      return;

    final int minesCount = getMinesCount(board, i, j);
    board[i][j] = minesCount == 0 ? 'B' : (char) ('0' + minesCount);

    if (minesCount == 0)
      for (int[] dir : dirs)
        dfs(board, i + dir[0], j + dir[1]);
  }

  private int getMinesCount(char[][] board, int i, int j) {
    int minesCount = 0;
    for (final int[] dir : dirs) {
      final int x = i + dir[0];
      final int y = j + dir[1];
      if (x < 0 || x == board.length || y < 0 || y == board[0].length)
        continue;
      if (board[x][y] == 'M')
        ++minesCount;
    }
    return minesCount;
  }
}

Python

class Solution:
  def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
    if board[click[0]][click[1]] == 'M':
      board[click[0]][click[1]] = 'X'
      return board

    dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1),
            (0, 1), (1, -1), (1, 0), (1, 1)]

    def getMinesCount(i: int, j: int) -> int:
      minesCount = 0
      for dx, dy in dirs:
        x = i + dx
        y = j + dy
        if x < 0 or x == len(board) or y < 0 or y == len(board[0]):
          continue
        if board[x][y] == 'M':
          minesCount += 1
      return minesCount

    def dfs(i: int, j: int) -> None:
      if i < 0 or i == len(board) or j < 0 or j == len(board[0]):
        return
      if board[i][j] != 'E':
        return

      minesCount = getMinesCount(i, j)
      board[i][j] = 'B' if minesCount == 0 else str(minesCount)

      if minesCount == 0:
        for dx, dy in dirs:
          dfs(i + dx, j + dy)

    dfs(click[0], click[1])

    return board