BOJ7562 나이트의 이동

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

import java.io.*;
import java.util.*;
public class Main
{   
    static int l;
	public static class Node{
	    int r;
	    int c;
	    int step;
	    
	    public Node(int r, int c, int step){
	        this.r=r;
	        this.c=c;
	        this.step =step;
	    }
	} 
	
	public static int bfs(Node start,Node end){
	    Queue<Node> q = new LinkedList();
	    boolean[][] visited= new boolean[l][l];
        q.offer(start);
        while(q.size()>0){
            Node node = q.poll();
            if(node.c==end.c && node.r==end.r){
                return node.step;
            }
            int[] move_r= {2,2,1,1,-1,-1,-2,-2};
            int[] move_c= {1,-1,2,-2,2,-2,1,-1};
            for(int i=0;i<move_r.length;i++){
                Node next= new Node(node.r+move_r[i], node.c+move_c[i], node.step+1);
                if(next.c>=0 && next.c<l&& next.r>=0 && next.r<l && !visited[next.r][next.c]){
                    q.offer(next);
                    visited[next.r][next.c]=true;
                }
                
            }
        }
	    return 0;
	}
		
    
    
    
    
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
        while(T-->0){
            
		    l = Integer.parseInt(br.readLine());
		    String[] input1 = br.readLine().split(" ");
		    String[] input2 = br.readLine().split(" ");
		    Node start= new Node(Integer.parseInt(input1[0]),Integer.parseInt(input1[1]),0);
		    Node end= new Node(Integer.parseInt(input2[0]),Integer.parseInt(input2[1]),0);
		    int ans = bfs(start,end);
            System.out.println(ans);
        }
		
		
		
		
		
		
	}
}