一、完整代码
public class Main {
static int bfs(char[][] map, Set from, String goal) {
if(from.contains(gola)) return 0;
Set set = new HashSet();
for(Object obj : from) {
String[] temp = ((String)obj).split(" ");
int y = Integer.parseInt(temp[0]);
int x = Integer.parseInt(temp[1]);
if(y > 0 && map[y-1][x] == ".") {
map[y-1][x] = "*";
set.add(y-1+","+x);
}
if(y < map.length-1 && map[y+1][x]) {
map[y+1][x] = "*";
set.add(y+1+","+x);
}
if(x > 0 && map[y][x-1]) {
map[y][x-1]="*";
set.add(y+","+x-1);
}
if(x < map[0].length-1 && map[y][x+1]) {
map[y][x+1] = "*";
set.add(y + "," + x+1);
}
}
if(set.isEmpty()) return -1;
int ans = bfs(map, set, goal);
if(ans < 0) return -1;
return ans+1;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
String[] temp = cin.nextLine.trim().split(" +");
int n = Integer.parseInt(temp[0]);
int m = Integer.parseInt(temp[1]);
char[][] map = new char[n][];
for(int i = 0; i < n; i++) {
map[i] = cin.nextLine().trim().toCharArray();
}
Set set = new HashSet();
set.add("0,0");
System.out.println(bfs(map,set,n-1+","+m-1));
}
}
二、处理输入
java对输入的处理相对简单,cin.nextLine()读进来的是一个String,只要根据需求,处理好String就好了
- 对于行数和列数
- 根据分隔符将String一分为二
- 将上一步的两个String存在一个String[]中
- 用Integer将String强转成int
- 对于整张地图
- 用二维字符数组存储整张地图
- 所以只需要将String转成一个字符串数组即可——toCharArray()方法
Scanner cin = new Scanner(System.in);
String[] temp = cin.nextLine().trim().split(" +");
int n = Integer.parseInt(temp[0]);
int m = Integer.parseInt(temp[1]);
char[][] map = new char[n][];
for(int i = 0; i < n; i++) {
map[i] = cin.nextLine().trim().toCharArray();
}
三、bfs
我个人觉得,bfs就像炸弹炸起的气浪,在这一点爆炸,推起气浪。
如果被推起的地方是爆炸的话,还会被引爆;如果是墙,那么气浪就被阻挡了。
我们每一轮维护一个set,表示这一轮被引爆的炸弹,这个set的作用也有点类似于二叉树层次遍历中的队列的作用。
这个set中的点,形象来说,它的意思是,这些点刚刚被上一轮气浪所引爆,在本轮递归中,它们将爆炸去引爆它们四周的点。
1、主函数中
从(0,0)开始,所以该点是起爆点。
Set set = new HashSet();
set.add(0+","+0);
System.out.println(bfs(map, set, n-1+","+m-1));
2、终止区
static int bfs(char[][] map, Set from, String goal) {
if(from.cotains(goal)) return 0;
//3、循环区
//4、处理区
}
道理很简单,如果goal已经被上一轮引爆了,那么不需要再做什么了。
3、循环区
在循环区中,我们将遍历整个set,将他们所能引爆的全部点作为下一轮的Set from
Set set = new Set();
for(Object obj:set) {
String[] temp = ((Stirng)objspilt(" ");
int y = Integer.parseInt(temp[0]);
int x = Integer.parseInt(temp[1]); //将Set from中的一组xy取出来
if(y > 0 && map[y-1][x] == '.') { //上方
map[y-1][x] = '*'; //做好标记,说明已经搜索过
set.add(y-1+","+x); //将其加入下一轮迭代的Set from中
}
if(y < map.length-1 && map[y+1][x] == '.') { //下方
map[y+1][x] = '*';
set.add(y+1+","+x);
}
if(x > 0 && map[x-1][y] == '.') { //左方
map[y][x-1] = '*';
set.add(y+","+x-1);
}
if(x < map[0].length-1 && map[x+1][y] == '.') { //右方
map[y][x-1] = '*';
set.add(y+","+x+1);
}
}
4、处理区
if(set.isEmpty()) return -1;
int ans = bfs(map, set, goal);
if(ans < 0) return -1;
return ans+1;
- 第一行
- 如果构造出来Set from为空,说明气浪到这里就失败了,推不动了
- 第二行
- 根据新构造出来的Set from,进行下一轮的递归
- 新一轮的递归可能失败可能成功
- 如果失败了,那就是第三行的情况
- 如果成功了,那就是第四行的情况,ans再加上从该点到下一轮迭代点的一步,往上返回