Advertisement
Guest User

Untitled

a guest
Aug 23rd, 2020
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.50 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayDeque;
  5. import java.util.Arrays;
  6. import java.util.Random;
  7. import java.util.StringTokenizer;
  8.  
  9. public class Main {
  10.  
  11.     static int h, w;
  12.     static char[][] board;
  13.    
  14.     public static void main(String[] args) {
  15.         FastScanner fs=new FastScanner();
  16.         h=fs.nextInt(); w=fs.nextInt();
  17.         int sy=fs.nextInt()-1, sx=fs.nextInt()-1;
  18.         int ey=fs.nextInt()-1, ex=fs.nextInt()-1;
  19.         ArrayDeque<Integer> xs=new ArrayDeque<>(), ys=new ArrayDeque<>();
  20.         board=new char[w][h];
  21.         for (int y=0; y<h; y++) {
  22.             char[] line=fs.next().toCharArray();
  23.             for (int x=0; x<w; x++) {
  24.                 board[x][y]=line[x];
  25.             }
  26.         }
  27.         xs.add(sx);
  28.         ys.add(sy);
  29.         int[][] dist=new int[w][h];
  30.         for (int x=0; x<w; x++) Arrays.fill(dist[x], 1_000_000_000);
  31.         dist[sx][sy]=0;
  32.         int[] dx= {-1, 1, 0, 0};
  33.         int[] dy= {0, 0, -1, 1};
  34.         while (!xs.isEmpty()) {
  35.             int curX=xs.removeFirst(), curY=ys.removeFirst();
  36.             for (int d=0; d<4; d++) {
  37.                 int nx=curX+dx[d], ny=curY+dy[d];
  38.                 if (!legal(nx, ny)) continue;
  39.                 if (dist[nx][ny]>dist[curX][curY]) {
  40.                     dist[nx][ny]=dist[curX][curY];
  41.                     xs.addFirst(nx);
  42.                     ys.addFirst(ny);
  43.                 }
  44.             }
  45.             for (int x=curX-2; x<=curX+2; x++) {
  46.                 for (int y=curY-2; y<=curY+2; y++) {
  47.                     if (!legal(x, y)) continue;
  48.                     if (dist[x][y]>dist[curX][curY]+1) {
  49.                         dist[x][y]=dist[curX][curY]+1;
  50.                         xs.addLast(x);
  51.                         ys.addLast(y);
  52.                     }
  53.                 }
  54.             }
  55.         }
  56.         System.out.println(dist[ex][ey]>1e7?-1:dist[ex][ey]);
  57.     }
  58.  
  59.     static boolean legal(int x, int y) {
  60.         if (x<0||y<0||x>=w||y>=h || board[x][y]=='#') return false;
  61.         return true;
  62.     }
  63.    
  64.     static final Random random=new Random();
  65.    
  66.     static void ruffleSort(int[] a) {
  67.         int n=a.length;//shuffle, then sort
  68.         for (int i=0; i<n; i++) {
  69.             int oi=random.nextInt(n), temp=a[oi];
  70.             a[oi]=a[i]; a[i]=temp;
  71.         }
  72.         Arrays.sort(a);
  73.     }
  74.    
  75.     static class FastScanner {
  76.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  77.         StringTokenizer st=new StringTokenizer("");
  78.         String next() {
  79.             while (!st.hasMoreTokens())
  80.                 try {
  81.                     st=new StringTokenizer(br.readLine());
  82.                 } catch (IOException e) {
  83.                     e.printStackTrace();
  84.                 }
  85.             return st.nextToken();
  86.         }
  87.        
  88.         int nextInt() {
  89.             return Integer.parseInt(next());
  90.         }
  91.         int[] readArray(int n) {
  92.             int[] a=new int[n];
  93.             for (int i=0; i<n; i++) a[i]=nextInt();
  94.             return a;
  95.         }
  96.         long nextLong() {
  97.             return Long.parseLong(next());
  98.         }
  99.     }
  100.  
  101.    
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement