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');
				 }
			 }