专栏首页机器学习入门挑战程序竞赛系列(5):2.1广度优先搜索

挑战程序竞赛系列(5):2.1广度优先搜索

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/72499714

2.1广度优先搜索

详细代码可以fork下Github上leetcode项目,不定期更新。

练习题如下: 1. AOJ 0558: Cheese 2. POJ 3669: Meteor Shower 3. AOJ 0121: Seven Puzzle

AOJ 0558: Cheese

翻译参考博文【AOJ 0558 Cheese 《挑战程序设计竞赛(第2版)》练习题答案

在H * W的地图上有N个奶酪工厂,分别生产硬度为1-N的奶酪。有一只吃货老鼠准备从老鼠洞出发吃遍每一个工厂的奶酪。老鼠有一个体力值,初始时为1,每吃一个工厂的奶酪体力值增加1(每个工厂只能吃一次),且老鼠只能吃硬度不大于当前体力值的奶酪。 老鼠从当前格走到相邻的无障碍物的格(上下左右)需要时间1单位,有障碍物的格不能走。走到工厂上时即可吃到该工厂的奶酪,吃奶酪时间不计。问吃遍所有奶酪最少用时。 输入:第一行三个整数H(1 <= H <= 1000)、W(1 <= W <=1000)、N(1 <= N <= 9),之后H行W列为地图, “.“为空地, ”X“为障碍物,”S“为老鼠洞, 1-N代表硬度为1-N的奶酪的工厂。

思路: 依次求出1…N的最短路径,单纯的累加即可。BFS遍历得始终注意遍历过的点不要再添加到队列中去,其他没什么,注意下queue.size()的小技巧,累加步数非常有用。代码如下:

public class SolutionDay18_A0558 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int H = in.nextInt();
        int W = in.nextInt();
        int N = in.nextInt();

        char[][] map = new char[H][W];
        for (int i = 0; i < H; i++) {
            char[] ss = in.next().trim().toCharArray();
            for (int j = 0; j < W; j++) {
                map[i][j] = ss[j];
            }
        }
        System.out.println(solve(map,N));
        in.close();
    }

    public static int solve(char[][] map, int N){
        int row = map.length;
        int col = map[0].length;
        int[][] factory = new int[N+1][2];
        for (int i = 0; i < row; i++){
            for (int j = 0; j <col; j++){
                if (map[i][j] == 'S'){
                    factory[0][0] = i;
                    factory[0][1] = j;
                }
                else if (map[i][j] != '.' && map[i][j] != 'X'){
                    factory[map[i][j]-'0'][0] = i;
                    factory[map[i][j]-'0'][1] = j;
                }
            }
        }
        int step = 0;
        for (int i = 0; i < N; i++){
            step += bfs(map, factory[i][0], factory[i][1], factory[i+1][0], factory[i+1][1]);
        }
        return step;
    }

    static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
    private static int bfs(char[][] map, int sx, int sy, int ex, int ey){
        int row = map.length, col = map[0].length;
        int[][] distance = new int[row][col];
        for (int i = 0; i < row; i++){
            Arrays.fill(distance[i], -1);
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sx, sy});
        distance[sx][sy] = 0;
        int step = 1;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++){
                int[] cur = queue.poll();
                for (int[] d : dir){
                    int nx = cur[0] + d[0];
                    int ny = cur[1] + d[1];
                    if (nx >= 0 && nx < row && ny >= 0 && ny < col && map[nx][ny] != 'X' && distance[nx][ny] == -1){
                        distance[nx][ny] = step;
                        queue.offer(new int[]{nx,ny});
                    }
                }
            }
            step++;
        }
        return distance[ex][ey];
    }
}

POJ 3669: Meteor Shower

有个小文青去看流星雨,不料流星掉下来会砸毁上下左右中五个点。每个流星掉下的位置和时间都不同,求小文青能否活命,如果能活命,最短的逃跑时间是多少?

思路: 把流行能击中的区域全部求出来,用最小达到的时刻记录下来,这样留给小文青的逃跑路线是最紧张的。而未被击中的地方可以用INF表示这些区域相当安全。所以如果小文青能够跑到一个INF的地方,那么这就意味着他安全了。代码如下:

public class SolutionDay18_P3669 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int M = in.nextInt();
        int[][] map = new int[M][2];
        int[] T = new int[M];
        for (int i = 0; i < M; i++){
            map[i][0] = in.nextInt();
            map[i][1] = in.nextInt();
            T[i] = in.nextInt();
        }
        System.out.println(solve(map, T));
        in.close();
    }

    static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1},{0,0}};
    static final int INF = 1 << 30;

    private static int solve(int[][] map, int[] T){
        int[][] distance = new int[512][512];
        int[][] hit = new int[512][512];

        for (int i = 0; i < distance.length; i++){
            Arrays.fill(distance[i], INF);
            Arrays.fill(hit[i], INF);
        }
        distance[0][0] = 0;
        int M = map.length;
        int last = T[0];
        for (int i = 0; i < M; i++){
            int x = map[i][0];
            int y = map[i][1];
            last = Math.max(last, T[i]);
            for (int[] d : dir){
                int nx = x + d[0];
                int ny = y + d[1];
                if (nx >= 0 && nx < 512 && ny >= 0 && ny < 512){
                    hit[nx][ny] = Math.min(hit[nx][ny], T[i]);
                }
            }
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0,0});
        if (hit[0][0] == 0) return -1; 

        int step = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            step++;
            for (int i = 0; i < size; i++){
                int[] cur = queue.poll();
                for (int k = 0; k < 4; k++){
                    int nx = cur[0] + dir[k][0];
                    int ny = cur[1] + dir[k][1];
                    if (nx >= 0 && nx < 512 && ny >= 0 && ny < 512 && step < hit[nx][ny] && distance[nx][ny] == INF){
                        distance[nx][ny] = step;
                        //关键,表示安全了,返回当前步数即可
                        if(hit[nx][ny] > last){
                            return step;
                        }
                        queue.offer(new int[]{nx,ny});
                    }
                }
            }
        }
        return -1;
    }
}

注意:step < hit[nx][ny]说明当step == hit[nx][ny],恰巧被砸中,所以不会被放入队列中作为候选路径。

AOJ 0121: Seven Puzzle

题目大意可参考博文【AOJ 0558 Cheese 《挑战程序设计竞赛(第2版)》练习题答案

思路: 该题的特点在于4*2的方框固定,所以我们完全可以构造解空间,而采用的手段是BFS,如何构造解空间,从初始数组”01234567”开始,寻找0的位置,让它与相邻位置交换,第二步继续寻找0的位置与相邻位置交换。而我们知道,在大量的交换过程中,会存在大量的重复解,遇到重复解,我们直接丢弃即可。所以队列是一个慢慢增大又慢慢减小的过程。

代码如下:

public class SolutionDay18_A0121 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Map<String,Integer> map = bfs();
        while(in.hasNext()){
            String key = "";
            for (int i = 0; i < 2; i++){
                for (int j = 0; j < 4; j++){
                    key += in.nextInt();
                }
            }
            System.out.println(map.get(key));
        }
        in.close();
    }

    static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
    private static Map<String, Integer> bfs(){
        Map<String, Integer> map = new HashMap<>();
        map.put("01234567", 0);
        char[][] init = {{'0','1','2','3'},{'4','5','6','7'}};
        Queue<char[][]> queue = new LinkedList<>();
        queue.offer(init);

        while (!queue.isEmpty()){
            char[][] now = queue.poll();
            String nows = "";

            int[] cur = new int[2];
            for (int i = 0; i < 2; i++){
                for (int j = 0; j < 4; j++){
                    nows += now[i][j]-'0';
                    if (now[i][j] == '0'){
                        cur[0] = i;
                        cur[1] = j;
                    }
                }
            }

            for (int[] d : dir){
                int nx = cur[0] + d[0];
                int ny = cur[1] + d[1];
                if (nx >= 0 && nx < 2 && ny >= 0 && ny < 4){
                    char[][] next = clone(now);
                    swap(next, cur[0], cur[1], nx, ny);
                    char[] ss = new char[8];
                    for (int i = 0, k = 0; i < 2; i++){
                        for (int j = 0; j < 4; j++){
                            ss[k++] = next[i][j];
                        }
                    }
                    String nn = new String(ss);
                    if (!map.containsKey(nn)){
                        map.put(nn, map.get(nows)+1);
                        queue.offer(next);
                    }
                }
            }
        }
        return map;
    }

    private static char[][] clone(char[][] now){
        int row = now.length;
        int col = now[0].length;
        char[][] clone = new char[row][col];
        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                clone[i][j] = now[i][j];
            }
        }
        return clone;
    }

    private static void swap(char[][] map, int x1, int y1, int x2, int y2){
        char tmp = map[x1][y1];
        map[x1][y1] = map[x2][y2];
        map[x2][y2] = tmp;
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法原理系列:木桶排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 挑战程序竞赛系列(36):3.3线段树和平方分割

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 挑战程序竞赛系列(21):3.2反转

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • GO-回调函数

    1,什么是回调函数。一个函数中有个参数为函数的指针。该函数自己调用自己指针函数即可; 2,为什么要使用回调函数。抽象画了一个函数,简洁代码。异步执行 3,例子:...

    李海彬
  • C语言第七讲,函数入门.

               C语言第七讲,函数入门. 一丶了解面向过程和面向对象的区别. 为什么要先讲面向过程和面向对象的区别? 面向过程,就是什么都要自己做.  比...

    IBinary
  • 洛谷P1333 瑞瑞的木棍(欧拉回路)

    题目描述 瑞瑞有一堆的玩具木棍,每根木棍的两端分别被染上了某种颜色,现在他突然有了一个想法,想要把这些木棍连在一起拼成一条线,并且使得木棍与木棍相接触的两端颜色...

    attack
  • NYOJ 139 我排第几个(康拓展开+康拓展开逆运算)

           康拓展开的裸题,对于康拓展开的定义是求当前的排列位于全排列中的第几个,比如132就是123的全排列的第二个,对于康拓展开的求法就是ans = ai...

    Ch_Zaqdt
  • 蓝桥杯--算法入门级题目及答案解析

    写在最前面: 本文中会出现大量的请查阅.请自学什么的,不是我不讲,本文是面向算法初学者和蓝桥杯的文章,如果真的想看进阶算法的也不会来看这些题目,所以不要介意,...

    风骨散人Chiam
  • 1001 舒适的路线 2006年

    1001 舒适的路线 2006年 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Descrip...

    attack
  • HDU 5677 ztr loves substring(回文串加多重背包)

    ztr loves substring Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 655...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券