46分!求求佬帮忙看看改改的
查看原帖
46分!求求佬帮忙看看改改的
1211502
TearsMeow楼主2024/4/17 00:52

后续我加了st[]数组之后也没有过更多数据,目前不太会改了。求大佬指点orz,orz orz,orz orz,orz

import java.io.*;
import java.util.*;

public class Main {
    static int N = 310,n,m;
    static Pair start,end;
    static int[][] d = new int[N][N],g = new int[N][N];
    static int[] dx= {-1,0,1,0},dy= {0,1,0,-1};
    static Pair[] pairs = new Pair[N * N];
    //定义一个数组用来存储传送门
    static Exch[] ex = new Exch[100];
    static int Int(String s){return Integer.parseInt(s);}
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args)throws IOException{
        String[] arrStr = br.readLine().split(" ");
        n = Int(arrStr[0]);m = Int(arrStr[1]);
        for(int i = 0;i < n;i++) {
        	arrStr = br.readLine().split("");
        	for(int j =0 ;j < m;j++) {
        		if("#".equals(arrStr[j])) {
        			g[i][j] = 0;
        		} else if ("@".equals(arrStr[j])) {
        			g[i][j] = 1; start = new Pair(i,j);
        		}else if (".".equals(arrStr[j])) g[i][j] = 1;
        		else if ("=".equals(arrStr[j])) {
        			g[i][j] = 1; end = new Pair(i,j);
        		}else {
        			char c = arrStr[j].charAt(0);
        			if(c <= 'A' || c >= 'Z') continue;
        			g[i][j] = c;
        			if(ex[c] == null) ex[c] = new Exch(0, 0, 0, 0);
        			if(ex[c].x1 == 0) {
        				ex[c].x1 = i;ex[c].y1 = j;
        			}else ex[c].x2 = i;ex[c].y2 = j;
        			
        		}
        		//将所有距离初始化置为-1
        		d[i][j] = -1;
        	}
        }
        
        int minTime = bfs(start.x,start.y);
        //输出最小步骤
        pw.println(minTime);

        pw.flush();br.close();pw.close();
    }
    static int bfs(int x,int y) {
    	int hh = 0 , tt= -1;
    	pairs[++tt] = new Pair(x,y);
    	d[x][y] = 0;
    	while(hh <= tt) {
    		Pair p = pairs[hh++];
    		for(int i =0;i < 4;i++) {
    			int xx = p.x + dx[i] ;int yy = p.y + dy[i];
                //如果当前坐标合法,并且第一次被更新到,并且读到的点不是障碍物
    			if(xx >= 0 && xx < n && yy >= 0 && yy < m && d[xx][yy] == -1 && g[xx][yy] > 0){					//获取读到的点的int值,如果1,那么就是可走的
    				int t = g[xx][yy];
    				//如果这个int值没有被记录过,说明不是传送门
                    //如果被记录过,说明要同时更新当前点,和传送点
    				if(ex[t] != null) {
                        //那么先把当前点加入
    					d[xx][yy] = d[p.x][p.y] + 1;
						pairs[++tt] = new Pair(xx,yy);
                        //判断如果当前点是第一个坐标,那么把第二个加入,否则把第一个加入
    					if(ex[t].x1 == xx && ex[t].y1 == yy) {
        					d[ex[t].x2][ex[t].y2] =  d[p.x][p.y] + 1;
        					pairs[++tt] = new Pair(ex[t].x2,ex[t].y2);
        					continue;
    					}else {
        					d[ex[t].x1][ex[t].y1] =  d[p.x][p.y] + 1;
        					pairs[++tt] = new Pair(ex[t].x1,ex[t].y1);
        					continue;
    					}
    				}
    				//如果不是传送门,正常逻辑
    				d[xx][yy] = d[p.x][p.y] + 1;
    				pairs[++tt] = new Pair(xx,yy);
    			}
    		}
    	}
    	return d[end.x][end.y];
    }

}
//传送门的两个坐标记录点exchange
class Exch{
	int x1;int x2;int y1;int y2;
	public Exch(int x1,int y1,int x2,int y2) {
		this.x1= x1;this.y1 = y1;
		this.x2 = x2 ;this.y2 = y2;
	}
}
//坐标
class Pair{
	int x;int y;
	public Pair(int x,int y) {
		this.x = x;
		this.y = y;
	}
}

2024/4/17 00:52
加载中...