[백준] 7562 : 나이트의 이동 -JAVA(자바) - 사좋배 공유

 

 

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

public class Main {
	static int dx[]= {-2,-1,1,2,2,1,-1,-2};
	static int dy[]= {1,2,2,1,-1,-2,-2,-1};
	static int [][]arr;
	static boolean [][]visit;
	static int chase_size;
	static Queueq;
	static int result;
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int test_case=Integer.parseInt(sc.nextLine());
		for(int t=0;t<test_case;t++) {
			chase_size= sc.nextInt();
			arr= new int[chase_size][chase_size];
			visit=  new boolean[chase_size][chase_size];
			q=new LinkedList();
			int startx=sc.nextInt();
			int starty=sc.nextInt();
			int desx =sc.nextInt();
			int desy =sc.nextInt();
			visit[startx][starty]=true;
			result=-1;
			q.add(new pos(startx,starty,0));
			arr[startx][starty]=1;
			arr[desx][desy]=2;
			BFS();
			System.out.println(result);
		}
	}
	public static void BFS() {
		while(!q.isEmpty()) {
			pos temp = q.poll();
			int x= temp.x;
			int y= temp.y;
			int count= temp.count;
			if(arr[x][y]==2) {
				result = count;
				q.clear();
				return;
			}
			for(int i=0;i<8;i++) {
				int rx= x+dx[i];
				int ry= y+dy[i];
				if(rx<0||ry<0||rx>=chase_size||ry>=chase_size||visit[rx][ry]==true) {
					continue;
				}
				if(visit[rx][ry]==false) {
					q.add(new pos(rx,ry,count+1));
					visit[rx][ry]=true;
				}

			}
		}
	}

}
class pos {
	int x;
	int y;
	int count;
	pos(int x, int y,int count){
		this.x=x;
		this.y=y;
		this.count = count;
	}
}