欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蓝桥杯_迷宫问题_宽搜

程序员文章站 2022-05-20 22:50:27
...

一、完整代码

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再加上从该点到下一轮迭代点的一步,往上返回