JavaBFS求调教 52分

P1825 [USACO11OPEN] Corn Maze S

没必要用Map的直接用数组就行了,从A到Z最多26对,直接数组实现 ```java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; public class Main { static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); static int X[] = new int[]{0,0,1,-1}; static int Y[] = new int[]{1,-1,0,0}; static int n,m; static char map[][]; static boolean check[][]; static int csm[][] = new int[26][4]; static int sx,sy,tx,ty; public static void main(String[] args) throws IOException { String s[] = bf.readLine().split(" "); n = Integer.parseInt(s[0]); m = Integer.parseInt(s[1]); map = new char[n+1][m+1]; check = new boolean[n+1][m+1]; for (int i = 1; i <= n; i++) { String str = bf.readLine(); for (int j = 1; j <= m; j++) { map[i][j] = str.charAt(j-1); if(map[i][j]>='A'&&map[i][j]<='Z'){ int loc = map[i][j] - 'A'; if(csm[loc][0]==0){ csm[loc][0] = i; csm[loc][1] = j; } else { csm[loc][2] = i; csm[loc][3] = j; } } if(map[i][j]=='@'){ sx = i; sy = j; } if(map[i][j]=='='){ tx = i; ty = j; } } } System.out.println(bfs()); } static int bfs(){ Queue<int[]> q = new LinkedList<>(); q.offer(new int[]{sx,sy}); int time = 0; check[sx][sy] = true; while (!q.isEmpty()){ int size = q.size(); while(size-->0){ int arr[] = q.poll(); int x = arr[0]; int y = arr[1]; if(x==tx&&y==ty){ return time; } if(map[x][y]>='A'&&map[x][y]<='Z'){ int loc = map[x][y] - 'A'; check[x][y] = true; if(x==csm[loc][0]&&y==csm[loc][1]){ x = csm[loc][2]; y = csm[loc][3]; } else { x = csm[loc][0]; y = csm[loc][1]; } } for (int i = 0; i < 4; i++) { int nx = x+X[i]; int ny = y+Y[i]; if(test(nx,ny)){ q.offer(new int[]{nx,ny}); check[nx][ny] = true; } } } time++; } return 0; } static boolean test(int x,int y){ if(x<1||x>n||y<1||y>m)return false; if(map[x][y]=='#')return false; if(check[x][y])return false; return true; } } ```
by _Yan @ 2023-05-29 11:02:24


|