BFS-洛谷迷宫（二）

Bertha 。 2023-07-12 05:07 20阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]**样例输入1**

3 4
    S**.
    ..*.
    ***T

**样例输出1**

-1

**样例输入2**

3 4
    S**.
    ....
    ***T

样例输出2

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class enen {
        
        static int n,m;
        static char[][]a=new char[15][15];
        static boolean [][]vis=new boolean[15][15];
        static int[][]dis={
        {
        0,0,1,-1},{
        1,-1,0,0}};
        static class node{
        
    
            public int x,y,s;
        }
        public static void bfs(int sx,int sy){
        
            Queue<node> queue=new LinkedList<node>();
            node p=new node();
            p.x=sx;p.y=sy;p.s=0;
            queue.offer(p);//加入一个元素
            while (!queue.isEmpty()){
        
                node now=queue.element();
                queue.poll();//删除第一个元素
                for (int i = 0; i <4 ; i++) {
        
                    int xx=now.x+dis[0][i];
                    int yy=now.y+dis[1][i];
                    if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&a[xx][yy]!='*'){
        
                        node pp=new node();
                        pp.x=xx; pp.y=yy;pp.s=now.s+1;
                        vis[xx][yy]=true;
                        queue.offer(pp);
                        if(a[xx][yy]=='T') {
        //谁先到达T就弹出，就可以到最小了
                            System.out.print(pp.s);
                            System.exit(0);
                        }
                    }
    
                }
            }
            System.out.println(-1);
    
        }
        public static void main(String[] args) {
        
            int sx=0,sy=0;
            Scanner scanner=new Scanner(System.in);
            n=scanner.nextInt();
            m=scanner.nextInt();
            for (int i = 1; i <=n ; i++) {
        
                String s=scanner.next();
                for (int j = 1; j <=m ; j++) {
        
                    a[i][j]=s.charAt(j-1);
                    if (a[i][j]=='S'){
        
                        sx=i;
                        sy=j;
                    }
                }
            }
            vis[sx][sy]=true;
            bfs(sx,sy);
        }
    }

# 队列先进先出，一条管子 #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200307084859169.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng==,size_16,color_FFFFFF,t_70