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 class Solution { public: vector> updateBoard(vector>& board, vector& 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> dirs{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}; void dfs(vector>& 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>& 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 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; } } 
  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]]: 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