529. 扫雷游戏 DFS

529. 扫雷游戏

2020/8/20每日一题打卡√

题目描述

解题思路

感觉这个题最难的点还是在于理解题意和样例

理解了之后就很明确了，就是正常的DFS

如果点击了雷，就爆炸

如果没点到雷，就判断这个位置旁边有没有雷；如果有雷，把这个位置设置成周围雷的数量

如果没有雷，把这个位置标记成B，然后递归的标记标记位置周围的位置

/*
			  * 529. 扫雷游戏
			  * 2020/8/20
			  * medium
			  */
			 public char[][] updateBoard(char[][] board, int[] click) {
				 int x = click[0],y = click[1];
				 if(board[x][y] == 'M') {//如果选中了地雷
					 board[x][y] = 'X';
				 }
				 else if(board[x][y] == 'E') { //如果选中的空方快，递归的修改其它方块
					 dfsUpdateBoard(board,x,y,board.length,board[0].length);
					 
				 }
				 return board;
			    }
			 
			 public void dfsUpdateBoard(char[][] board,int x,int y,int m,int n) {
				 //8个方向
				 int xShift[] = {-1,-1,-1,0,0,1,1,1};
				 int yShift[] = {-1,0,1,-1,1,-1,0,1};
				 //如果不满足条件直接返回
				 if(x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'E') {
					 return;
				 }
				 //统计这个节点周围有多少个地雷
				 int count = 0;
				 for (int i = 0; i < yShift.length; i++) {
					int xx = x + xShift[i];
					int yy = y + yShift[i];
					if(xx >= 0 && xx < m && yy >= 0 && yy < n && board[xx][yy] == 'M') {
						count++;
					}
				}
				 //如果四周没有地雷，修改这个节点的值，并递归的点击四周
				 if(count == 0) {
					 board[x][y] = 'B';
					 for (int i = 0; i < yShift.length; i++) {
							int xx = x + xShift[i];
							int yy = y + yShift[i];
							if(xx >= 0 && xx < m && yy >= 0 && yy < n && board[xx][yy] == 'E') {
								dfsUpdateBoard(board,xx,yy,m,n);
							}
				     }
				 }else {//如果和地雷相邻，修改距离
					 board[x][y] = (char) (count + '0');
				 }
			 }