前言
??????DFS 和 BFS，可参考之前的一篇文章：https://blog.csdn.net/Little_ant_/article/details/123415889?spm=1001.2014.3001.5501 介绍了二者的伪代码实现和关于 BFS 实现时需要注意的地方。
扫雷游戏
??????题目链接：https://leetcode-cn.com/problems/minesweeper/
??????题目描述：
让我们一起来玩扫雷游戏！
给你一个大小为 m x n 二维字符矩阵 board ，表示扫雷游戏的盘面，其中：
‘M’ 代表一个 未挖出的 地雷，
‘E’ 代表一个 未挖出的 空方块，
‘B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块，
数字（‘1’ 到 ‘8’）表示有多少地雷与这块 已挖出的 方块相邻，
‘X’ 则表示一个 已挖出的 地雷。
给你一个整数数组 click ，其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（‘M’ 或者 ‘E’）中的下一个点击位置（clickr 是行下标，clickc 是列下标）。
根据以下规则，返回相应位置被点击后对应的盘面：
如果一个地雷（‘M’）被挖出，游戏就结束了- 把它改为 ‘X’ 。
如果一个 没有相邻地雷 的空方块（‘E’）被挖出，修改它为（‘B’），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
如果一个 至少与一个地雷相邻 的空方块（‘E’）被挖出，修改它为数字（‘1’ 到 ‘8’ ），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回盘面。
DFS ：
??????思路为：1，如果当前位置元素为’M’，修改其为’X‘并返回；如果为’E’的话，这里注意和简单的 DFS 有点差异，区别在于简单的 DFS 这时便可以对当前位置元素做访问或修改，但是本题中需要首先判断当前位置周围 8 个元素的状态，然后根据结果来对当前位置进行修改。2，根据题意，DFS 递归的情况仅针对于当前位置为’B’的情况，相对的是如果当前位置为数字的话，不需要进行递归了。参考代码如下：
int[] xi={1,0,0,-1,1,1,-1,-1};
int[] yi={0,1,-1,0,-1,1,-1,1};
public char[][] updateBoard(char[][] board, int[] click) {
int x=click[0],y=click[1];
if(board[x][y]=='M'){
board[x][y]='X';
return board;
}
solve(board,x,y);
return board;
}
public void solve(char[][] board,int x,int y){
int count=0;
for(int i=0;i<8;i++){
int newX=x+xi[i],newY=y+yi[i];
if(newX<0||newY<0||newX>=board.length||newY>=board[0].length)
continue;
if(board[newX][newY]=='M')
count++;
}
if(count!=0)
board[x][y]=(char)('0'+count);
else{
board[x][y]='B';
for(int i=0;i<8;i++){
int newX=x+xi[i],newY=y+yi[i];
if(newX<0||newY<0||newX>=board.length||newY>=board[0].length)
continue;
if(board[newX][newY]=='E')
solve(board,newX,newY);
}
}
}
BFS
?????? BFS 中，为了避免相同元素重复入队有两种解决方法：1，在入队时修改其值，2，采用标记数组。本题没法在入队时修改其值，所以采用标记数组的方法（在入队时标记）。此问题在博客https://blog.csdn.net/Little_ant_/article/details/123415889?spm=1001.2014.3001.5501有提到过。参考代码如下：
public char[][] updateBoard(char[][] board, int[] click) {
int[] xi={1,0,0,-1,1,1,-1,-1};
int[] yi={0,1,-1,0,-1,1,-1,1};
int x=click[0],y=click[1];
LinkedList<int[]> queue=new LinkedList<>();
queue.add(new int[]{x,y});
if(board[x][y]=='M'){
queue.remove();
board[x][y]='X';
}
int count;
boolean[][] flag=new boolean[board.length][board[0].length];
flag[x][y]=true;
while(!queue.isEmpty()){
int[] tmp=queue.poll();
x=tmp[0];
y=tmp[1];
count=0;
for(int i=0;i<8;i++){
int newX=x+xi[i],newY=y+yi[i];
if(newX<0||newY<0||newX>=board.length||newY>=board[0].length)
continue;
if(board[newX][newY]=='M')
count++;
}
if(count!=0)
board[x][y]=(char)('0'+count);
else{
board[x][y]='B';
for(int i=0;i<8;i++){
int newX=x+xi[i],newY=y+yi[i];
if(newX<0||newY<0||newX>=board.length||newY>=board[0].length||flag[newX][newY])
continue;
if(board[newX][newY]=='E'){
queue.add(new int[]{newX,newY});
flag[newX][newY]=true;
}
}
}
}
return board;
}
总结
??????完
|