[BOJ] 7562. 나이트의 이동

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static Scanner sc=new Scanner(System.in);
	static int T=sc.nextInt();
	static int I;
	static int dx[]= {2,1,-1,-2,-2,-1,1,2};
	static int dy[]= {1,2,2,1,-1,-2,-2,-1};
	static int dist[][];
	static Point start;
	static Point end;
	
	public static void main(String[] args) {
		for (int t = 0; t < T; t++) {
			I=sc.nextInt();
			dist=new int[I][I];
			start=new Point(sc.nextInt(),sc.nextInt());
			end=new Point(sc.nextInt(),sc.nextInt());
			System.out.println(bfs(start.x,start.y));
		}
	}
	
	public static int bfs(int x,int y) {
		Queue<Point> q=new LinkedList<>();
		q.add(new Point(x,y));
		dist[x][y]=0;
		while(!q.isEmpty()) {
			Point c=q.poll();
			if(c.x==end.x && c.y==end.y) {
				return dist[c.x][c.y];
			}
			int nx,ny;
			for (int i = 0; i < 8; i++) {
				nx=c.x+dx[i];
				ny=c.y+dy[i];
				if(nx < 0 || ny < 0 || nx > I-1 || ny > I-1) continue;
				if(dist[nx][ny]==0) {
					dist[nx][ny]=dist[c.x][c.y]+1;
					q.add(new Point(nx,ny));
				}
			}
		}
		return 0;
	}
	
	public static class Point{
		int x,y;
		Point(int x, int y){
			this.x=x;
			this.y=y;
		}
	}
}