BFS
import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int[] dr = {-2,-2,-1,1,2,2,1,-1}; static int[] dc = {-1,1,2,2,1,-1,-2,-2}; static boolean[][] vis = new boolean[9][9]; static int ans; static int start_x,start_y,end_x,end_y; public static void main(String[] args) { Scanner scan = new Scanner(System.in); while(scan.hasNext()){ for(int i=1;i<=8;i++){ Arrays.fill(vis[i], false); } String start = scan.next(); String end = scan.next(); start_x = start.charAt(0)-'a'+1; start_y = 9-(start.charAt(1)-'0'); end_x = end.charAt(0)-'a'+1; end_y = 9-(end.charAt(1)-'0'); Queue<Node> q = new LinkedList<>(); Node u = new Node(start_x,start_y,0); q.add(u); while(!q.isEmpty()){ u = q.poll(); if(u.r==end_x&&u.c==end_y){ System.out.printf("To get from %s to %s takes %d knight moves.\n",start,end,u.d); break; } for(int i=0;i<8;i++){ int r = u.r+dr[i]; int c = u.c+dc[i]; if(inside(r,c)){ q.add(new Node(r,c,u.d+1)); } } } } } public static boolean inside(int r,int c){ return r>=1&&r<=8&&c>=1&&c<=8; } static class Node{ int r,c,d; public Node(int r,int c,int d){ this.r = r; this.c = c; this.d = d; } } }
