Skip to content

529. Minesweeper

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
 public:
  vector<vector<char>> updateBoard(vector<vector<char>>& board,
                                   vector<int>& click) {
    const int i = click[0];
    const int j = click[1];
    if (board[i][j] == 'M') {
      board[i][j] = 'X';
      return board;
    }

    dfs(board, i, j);
    return board;
  }

 private:
  static constexpr int dirs[8][2] = {{-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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
  public char[][] updateBoard(char[][] board, int[] click) {
    final int i = click[0];
    final int j = click[1];
    if (board[i][j] == 'M') {
      board[i][j] = 'X';
      return board;
    }

    dfs(board, i, j);
    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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
  def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
    i, j = click
    if board[i][j] == 'M':
      board[i][j] = '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(i, j)
    return board