Minesweeper
扫雷游戏, 给一个board给一个操作, 问操作过后的board什么样子. 这个就是dfs, 注意一点如果周围有雷, 需要用count记录一下雷数, 然后把count写入board.
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 47 48 |
public class Solution { public char[][] updateBoard(char[][] board, int[] click) { int m = board.length; int n = board[0].length; int row = click[0]; int col = click[1]; int[][] dirs = new int[][]{ {-1,-1}, {-1,0}, {1,0}, {-1, 1}, {1, -1}, {1,1}, {0,1}, {0, -1} }; if (board[row][col] == 'M') { // Mine board[row][col] = 'X'; } else { // Empty // Get number of mines first. int count = 0; for (int[] d : dirs) { int r = row + d[0], c = col + d[1]; if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue; if (board[r][c] == 'M' ) count++; } if (count > 0) { // If it is not a 'B', stop further DFS. board[row][col] = (char)(count + '0'); } else { // Continue DFS to adjacent cells. board[row][col] = 'B'; for (int[] d : dirs) { int r = row + d[0], c = col + d[1]; if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue; if (board[r][c] == 'E') updateBoard(board, new int[] {r, c}); } } } return board; } } |