Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayDeque;
- import java.util.HashMap;
- import java.util.Map;
- import java.util.Queue;
- import java.util.Scanner;
- public class SP {
- static final int[] dx = { 2, 2, -2, -2, 1, 1, -1, -1 };
- static final int[] dy = { 1, -1, 1, -1, -2, 2, 2, -2 };
- static int N;
- public static void main(String[] args) {
- Scanner scan = new Scanner(System.in);
- N = scan.nextInt();
- Queue<Node> q = new ArrayDeque<>();
- q.add(new Node(scan.nextInt(), scan.nextInt()));
- Node dest = new Node(scan.nextInt(), scan.nextInt());
- Map<Node, Boolean> vis = new HashMap<>();
- while (!q.isEmpty()) {
- Node tmp = q.poll();
- int x = tmp.x, y = tmp.y, dist = tmp.dist;
- // System.out.println("x:" + x + "\ny:" + y);
- if (x == dest.x && y == dest.y) {
- System.out.println(dist);
- return;
- }
- for (int i = 0; i < 8; i++) {
- int tx = x + dx[i];
- int ty = y + dy[i];
- Node nei = new Node(tx,ty,dist+1);
- boolean visTmp = vis.getOrDefault(nei, false);
- if (valid(tx, ty) && !visTmp) {
- q.add(nei);
- vis.put(nei, true);
- }
- }
- }
- System.out.println("Inf");
- }
- private static boolean valid(int tx, int ty) {
- return tx >= 0 && tx < N && ty >= 0 && ty < N;
- }
- }
- class Node {
- // dist represents distance from source
- int x, y, dist;
- Node(int x, int y, int dist) {
- this.x = x;
- this.y = y;
- this.dist = dist;
- }
- Node(int x, int y) {
- this.x = x;
- this.y = y;
- }
- @Override
- public boolean equals(Object obj) {
- if (this == obj)
- return true;
- if (obj == null || this.getClass() != obj.getClass())
- return false;
- Node other = (Node) obj;
- return this.x == other.x && this.y == other.y ? this.dist == other.dist : false;
- }
- @Override
- public int hashCode() {
- int res = x;
- res = 31 * res + y;
- res = 31 * res + dist;
- return res;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement