美文网首页
第18章 广度优先搜索

第18章 广度优先搜索

作者: 得力小泡泡 | 来源:发表于2020-04-03 15:42 被阅读0次

    1、哆啦A梦的时光机

    算法分析

    题目讲述一共有4种移动情况且权重一致

    • X 移动到 X−1
    • X 移动到 X+1
    • X 移动到 2∗X

    • X是偶数,从 X 移动到 2∗X

    相当于XX - 1,X + 1,2 * X ,各连一条边,从n开始进行bfskdist[k]表示k点到n点的最短距离

    时间复杂度 O(k)

    Java 代码

    import java.util.Arrays;
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    import java.util.Set;
    
    public class Main {
        static int N = 1000010;
        static int n;
        static int k;
        static int[] dist = new int[N];
        static int bfs()
        {
            Queue<Integer> q = new LinkedList<Integer>();
            Arrays.fill(dist, -1);
            q.add(n);
            dist[n] = 0;
            while(!q.isEmpty())
            {
                int t = q.poll();
                if(t - 1 >= 1 && dist[t - 1] == -1)
                {
                    dist[t - 1] = dist[t] + 1;
                    if(t - 1 == k) return dist[t - 1];
                    q.add(t - 1);
                }
                if(t + 1 < N && dist[t + 1] == -1)
                {
                    dist[t + 1] = dist[t] + 1;
                    if(t + 1 == k) return dist[t + 1];
                    q.add(t + 1);
                }
                if(t * 2 < N && dist[t * 2] == -1)
                {
                    dist[t * 2] = dist[t] + 1;
                    if(t * 2 == k) return dist[t * 2];
                    q.add(t * 2);
                }
                if(t % 2 == 0 && t / 2 >= 1 && dist[t / 2] == -1)
                {
                    dist[t / 2] = dist[t] + 1;
                    if(t / 2 == k) return dist[t / 2];
                    q.add(t / 2);
                }
            }
            return  -1;
        }
        public static void main(String[] args){
            Scanner scan = new Scanner(System.in);
            int T = scan.nextInt();
            while(T -- > 0)
            {
                n = scan.nextInt();
                k = scan.nextInt();
                System.out.println(bfs() * 2);
            }
            
        }
    }
    
    

    2、一维跳棋

    算法分析

    时间复杂度 O(k)

    Java 代码

    3、蒜头君回家

    算法分析

    求出起始位置start到所有点的最短距离,再求出终点位置end到所有点的最短距离,跑两次bfs,枚举所有的P点,则从起点到P点再回到终点的距离为dist1[i][j] + dist2[i][j],更新ans找到所有路径的最小值

    时间复杂度 O(nm)

    Java 代码

    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class Main {
        static int N = 2010;
        static int n,m;
        static char[][] g = new char[N][N];
        static Pair start,end;
        static int ans = 0;
        static int[][] dist1 = new int[N][N];//记录start到所有点的最短距离
        static int[][] dist2 = new int[N][N];//记录end到所有点的最短距离
        static int[] dx = new int[] {0,-1,0,1};
        static int[] dy = new int[] {-1,0,1,0};
        static void bfs(Pair start,int[][] dist)
        {
            for(int i = 0;i < n;i ++) Arrays.fill(dist[i], -1);
            Queue<Pair> q = new LinkedList<Pair>();
            dist[start.x][start.y] = 0;
            q.add(start);
            while(!q.isEmpty())
            {
                Pair t = q.poll();
                for(int i = 0;i < 4;i ++)
                {
                    int a = t.x + dx[i];
                    int b = t.y + dy[i];
                    if(a < 0 || a >= n || b < 0 || b >= m) continue;
                    if(dist[a][b] == -1 && g[a][b] != '#')
                    {
                        dist[a][b] = dist[t.x][t.y] + 1;
                        q.add(new Pair(a,b));
                    }
                }
            }
        }
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            n = scan.nextInt();
            m = scan.nextInt();
            for(int i = 0;i < n;i ++)
            {
                char[] temp = scan.next().toCharArray();
                for(int j = 0;j < m;j ++)
                {
                    g[i][j] = temp[j];
                    if(g[i][j] == 'S') start = new Pair(i,j);
                    if(g[i][j] == 'T') end = new Pair(i,j);
                }
            }
            bfs(start,dist1);
            bfs(end,dist2);
            int ans = Integer.MAX_VALUE;
            for(int i = 0;i < n;i ++)
                for(int j = 0;j < m;j ++)
                {
                    if(g[i][j] == 'P' && dist1[i][j] != -1 && dist2[i][j] != -1)
                    {
                        ans = Math.min(ans, dist1[i][j] + dist2[i][j]);
                    }
                }
            
            System.out.println(ans);
        }
    }
    class Pair
    {
        int x,y;
        Pair(int x,int y)
        {
            this.x = x;
            this.y = y;
        }
    }
    

    4、密码锁

    算法分析

    此题是求棋盘外的状态的最短路径问题,当前点到下面可以连上的点连上一个权值为1的边

    • 1、将任何一位数字加1
    • 2、将任何一位数字减1
    • 3、交换相邻的数字

    时间复杂度 线性复杂度

    Java 代码

    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.Map;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class Main {
        static String start;
        static String end;
        static Map<String,Integer> dist = new HashMap<String,Integer>();
        static String add(String s,int u)
        {
            String res = "";
            for(int i = 0;i < 4;i ++)
            {
                if(i == u)
                {
                    int x = s.charAt(u) - '0' + 1;
                    if(x == 10) x = 1;
                    res += x;
                }
                else res += s.charAt(i);
            }
            return res;
        }
        static String sub(String s,int u)
        {
            String res = "";
            for(int i = 0;i < 4;i ++)
            {
                if(i == u)
                {
                    int x = s.charAt(u) - '0' - 1;
                    if(x == 0) x = 9;
                    res += x;
                }
                else res += s.charAt(i);
            }
            return res;
        }
        static String swap(String s,int u)
        {
            char[] temp = s.toCharArray();
            char t = temp[u];
            temp[u] = temp[u + 1];
            temp[u + 1] = t;
            return String.valueOf(temp);
        }
        static int bfs()
        {
            Queue<String> q = new LinkedList<String>();
            q.add(start);
            dist.put(start, 0);
            while(!q.isEmpty())
            {
                String t = q.poll();
                //将任何一位数字加1
                for(int i = 0;i < 4;i ++)
                {
                    String s1 = add(t,i);
                    if(dist.containsKey(s1)) continue;
                    q.add(s1);
                    dist.put(s1, dist.get(t) + 1);
                    if(s1.equals(end)) return dist.get(end);
                }
                //将任何一位数字减1
                for(int i = 0;i < 4;i ++)
                {
                    String s2 = sub(t,i);
                    if(dist.containsKey(s2)) continue;
                    q.add(s2);
                    dist.put(s2, dist.get(t) + 1);
                    if(s2.equals(end)) return dist.get(end);
                }
                //交换相邻的数字
                for(int i = 0;i < 3;i ++)
                {
                    String s3 = swap(t,i);
                    if(dist.containsKey(s3)) continue;
                    q.add(s3);
                    dist.put(s3, dist.get(t) + 1);
                    if(s3.equals(end)) return dist.get(end);
                }
            }
            return -1;
        }
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            start = scan.next();
            end = scan.next();
            System.out.println(bfs());
        }
    }
    

    相关文章

      网友评论

          本文标题:第18章 广度优先搜索

          本文链接:https://www.haomeiwen.com/subject/iualuhtx.html