第六个点和第14个点过不去,求大佬指点
查看原帖
第六个点和第14个点过不去,求大佬指点
462645
溶金落梧桐楼主2022/1/30 00:16

import java.util.*;


public class Main {
    static char g[][]=new char[505][505];
    static int dis[][]=new int[505][505];
    static boolean st[][]=new boolean[304][304];
    static List<Point>[] pos=new List[28];
    static class Point{
        int x,y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int n,m;
    static Point start,ed;
    static int dx[]={0,1,0,-1};
    static int dy[]={1,0,-1,0};
    static void bfs(){
        Queue<Point> q=new LinkedList<>();
        for(int v[]:dis) Arrays.fill(v,-1);
        dis[start.x][start.y]=0;
        q.offer(start);
        while (!q.isEmpty()){
            Point t=q.poll();
            for(int i=0;i<4;i++){
                int x=t.x+dx[i];
                int y=t.y+dy[i];
                if(x<0||x>=n||y<0||y>=m||g[x][y]=='#'||st[x][y]) continue;
                dis[x][y]=dis[t.x][t.y]+1;
                st[x][y]=true;
                if(g[x][y]<='Z'&&g[x][y]>='A'){
                    List<Point> temp=new ArrayList<>(pos[g[x][y]-'A']);
                    for(int j=0;j<temp.size();j++){
                        Point p=temp.get(j);
                        if(!(p.x==x&&p.y==y)){
                            q.offer(p);
                            dis[p.x][p.y]=dis[t.x][t.y]+1;
                        }
                    }
                    continue;
                }
                q.offer(new Point(x,y));
            }
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n=in.nextInt();
        m=in.nextInt();
        for(int i=0;i<pos.length;i++) pos[i]=new ArrayList<>();
        for(int i=0;i<n;i++){
            String line=in.next();
            for(int j=0;j<m;j++){
                g[i][j]=line.charAt(j);
                if(g[i][j]=='@'){
                    start=new Point(i,j);
                }
                if(g[i][j]=='='){
                    ed=new Point(i,j);
                }
                if((g[i][j]<='Z'&&g[i][j]>='A')){
                    pos[g[i][j]-'A'].add(new Point(i,j));
                }
            }
        }
        bfs();
        System.out.println(dis[ed.x][ed.y]);
    }
}

2022/1/30 00:16
加载中...