Advertisement
Guest User

Untitled

a guest
Oct 16th, 2018
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.88 KB | None | 0 0
  1. import java.util.ArrayDeque;
  2. import java.util.HashMap;
  3. import java.util.Map;
  4. import java.util.Queue;
  5. import java.util.Scanner;
  6.  
  7. public class SP {
  8.  
  9.     static final int[] dx = { 2, 2, -2, -2, 1, 1, -1, -1 };
  10.     static final int[] dy = { 1, -1, 1, -1, -2, 2, 2, -2 };
  11.  
  12.     static int N;
  13.  
  14.     public static void main(String[] args) {
  15.  
  16.         Scanner scan = new Scanner(System.in);
  17.  
  18.         N = scan.nextInt();
  19.  
  20.         Queue<Node> q = new ArrayDeque<>();
  21.  
  22.         q.add(new Node(scan.nextInt(), scan.nextInt()));
  23.  
  24.         Node dest = new Node(scan.nextInt(), scan.nextInt());
  25.  
  26.         Map<Node, Boolean> vis = new HashMap<>();
  27.  
  28.         while (!q.isEmpty()) {
  29.  
  30.             Node tmp = q.poll();
  31.  
  32.             int x = tmp.x, y = tmp.y, dist = tmp.dist;
  33.  
  34. //          System.out.println("x:" + x + "\ny:" + y);
  35.             if (x == dest.x && y == dest.y) {
  36.                 System.out.println(dist);
  37.                 return;
  38.             }          
  39.  
  40.             for (int i = 0; i < 8; i++) {
  41.                 int tx = x + dx[i];
  42.                 int ty = y + dy[i];
  43.                
  44.                 Node nei = new Node(tx,ty,dist+1);
  45.                 boolean visTmp = vis.getOrDefault(nei, false);
  46.                
  47.                 if (valid(tx, ty) && !visTmp) {
  48.                     q.add(nei);
  49.                     vis.put(nei, true);
  50.                 }
  51.                    
  52.             }
  53.  
  54.         }
  55.         System.out.println("Inf");
  56.     }
  57.  
  58.     private static boolean valid(int tx, int ty) {
  59.         return tx >= 0 && tx < N && ty >= 0 && ty < N;
  60.     }
  61. }
  62.  
  63. class Node {
  64.  
  65.     // dist represents distance from source
  66.     int x, y, dist;
  67.  
  68.     Node(int x, int y, int dist) {
  69.         this.x = x;
  70.         this.y = y;
  71.         this.dist = dist;
  72.     }
  73.  
  74.     Node(int x, int y) {
  75.         this.x = x;
  76.         this.y = y;
  77.     }
  78.  
  79.     @Override
  80.     public boolean equals(Object obj) {
  81.         if (this == obj)
  82.             return true;
  83.         if (obj == null || this.getClass() != obj.getClass())
  84.             return false;
  85.  
  86.         Node other = (Node) obj;
  87.  
  88.         return this.x == other.x && this.y == other.y ? this.dist == other.dist : false;
  89.  
  90.     }
  91.  
  92.     @Override
  93.     public int hashCode() {
  94.         int res = x;
  95.         res = 31 * res + y;
  96.         res = 31 * res + dist;
  97.  
  98.         return res;
  99.     }
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement