링크

나이트의 이동-7562

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int arr[][];
	public static int count[][];
	public static int dx[] = {-2,-1,1,2,2,1,-1,-2};
	public static int dy[] = {1,2,2,1,-1,-2,-2,-1};
	
	public static int X;
	public static int num1;
	public static int num2;
	public static int result1;
	public static int result2;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		
		for(int i=0; i<n; i++)
		{
			X=Integer.parseInt(br.readLine());
			arr=new int[X][X];
			count=new int[X][X];
			
			StringTokenizer st=new StringTokenizer(br.readLine());
			num1=Integer.parseInt(st.nextToken());
			num2=Integer.parseInt(st.nextToken());
			
			StringTokenizer st1=new StringTokenizer(br.readLine());
			result1=Integer.parseInt(st1.nextToken());
			result2=Integer.parseInt(st1.nextToken());
			
			BFS(num1, num2);
			
		}
	}
	
	public static void BFS(int x, int y)
	{
		Queue<int[]> q=new LinkedList<int[]>();
		q.offer(new int[] {x, y});
		
		while(!q.isEmpty())
		{
			int now[]=q.poll();
			int nowx=now[0];
			int nowy=now[1];
			
			if(nowx==result1 && nowy==result2)
			{
				System.out.println(count[nowx][nowy]);
				return ;
			}
			
			for(int i=0; i<8; i++)
			{
				int nx=nowx+dx[i];
				int ny=nowy+dy[i];
				
				if(nx<=-1 || nx>=X || ny<=-1 || ny>=X)
					continue;
				
				if(count[nx][ny]==0)
				{
					count[nx][ny]=count[nowx][nowy]+1;
					q.offer(new int[] {nx, ny});
				}
			}
		
		}
	}
}