马走日
问题描述：
在中国象棋里，马的走棋要遵循“马走日”的规则，在本题中，给定马的起始位置，以及一个目标位置，判定该马是否能够走到该位置，如果能走到，最少步数是多少。（假设棋盘上只有一匹马，没有其他棋子）
输入描述：
输入文件中包含多个测试数据。每个测试数据为4个整数，si sj di dj，前两个整数为马的初始位置，后两个整数为目标位置，si和di的范围是[1,10]，sj dj的范围是[1,9]。输入文件中最后一行为4个0，代表输入结束。
输出描述：
对于每个测试数据，如果能到达目标位置，输出最少步数：如果不能达到，则输出0。
样例输入：
1 2 8 9
1 8 2 4
10 2 7 8
10 8 6 5
0 0 0 0
样例输出：
6
3
3
3
Code:
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Node{
//坐标类
public int x;
public int y;
public Node(int x,int y){
this.x = x;
this.y = y;
}
}
public class Main{
public static boolean[][] visited;
public static int[][] dp;
public static Queue<Node> queue = new LinkedList<>();
public Main() {
visited = new boolean[11][10];
dp = new int[11][10];
for(int i = 1;i<=10;i++){
for(int j = 1;j<=9;j++){
visited[i][j] = false;
dp[i][j] = 65535;
}
}
}
public static void BFS(int x1,int y1,int x2,int y2){
//广度优先搜索
Node node = new Node(x1,y1);
visited[x1][y1] = true;
dp[x1][y1] = 0;
queue.add(node);
while(!queue.isEmpty()){
Node frontNode = queue.poll();
if(frontNode.x-1>0&&frontNode.y-2>0&&visited[frontNode.x-1][frontNode.y-2]==false){
//左上1
visited[frontNode.x-1][frontNode.y-2] = true;
queue.add(new Node(frontNode.x-1,frontNode.y-2));
dp[frontNode.x-1][frontNode.y-2] = Math.min(dp[frontNode.x-1][frontNode.y-2],dp[frontNode.x][frontNode.y]+1);
}
if(frontNode.x+1<11&&frontNode.y-2>0&&visited[frontNode.x+1][frontNode.y-2]==false){
//右上1
visited[frontNode.x+1][frontNode.y-2] = true;
queue.add(new Node(frontNode.x+1,frontNode.y-2));
dp[frontNode.x+1][frontNode.y-2] = Math.min(dp[frontNode.x+1][frontNode.y-2],dp[frontNode.x][frontNode.y]+1);
}
if(frontNode.x+2<11&&frontNode.y-1>0&&visited[frontNode.x+2][frontNode.y-1]==false){
//右上2
visited[frontNode.x+2][frontNode.y-1] = true;
queue.add(new Node(frontNode.x+2,frontNode.y-1));
dp[frontNode.x+2][frontNode.y-1] = Math.min(dp[frontNode.x+2][frontNode.y-1],dp[frontNode.x][frontNode.y]+1);
}
if(frontNode.x-2>0&&frontNode.y-1>0&&visited[frontNode.x-2][frontNode.y-1]==false){
//左上2
visited[frontNode.x-2][frontNode.y-1] = true;
queue.add(new Node(frontNode.x-2,frontNode.y-1));
dp[frontNode.x-2][frontNode.y-1] = Math.min(dp[frontNode.x-2][frontNode.y-1],dp[frontNode.x][frontNode.y]+1);
}
if(frontNode.x-2>0&&frontNode.y+1<10&&visited[frontNode.x-2][frontNode.y+1]==false){
//左下1
visited[frontNode.x-2][frontNode.y+1] = true;
queue.add(new Node(frontNode.x-2,frontNode.y+1));
dp[frontNode.x-2][frontNode.y+1] = Math.min(dp[frontNode.x-2][frontNode.y+1],dp[frontNode.x][frontNode.y]+1);
}
if(frontNode.x-1>0&&frontNode.y+2<10&&visited[frontNode.x-1][frontNode.y+2]==false){
//左下2
visited[frontNode.x-1][frontNode.y+2] = true;
queue.add(new Node(frontNode.x-1,frontNode.y+2));
dp[frontNode.x-1][frontNode.y+2] = Math.min(dp[frontNode.x-1][frontNode.y+2],dp[frontNode.x][frontNode.y]+1);
}
if(frontNode.x+2<11&&frontNode.y+1<10&&visited[frontNode.x+2][frontNode.y+1]==false){
//右下1
visited[frontNode.x+2][frontNode.y+1] = true;
queue.add(new Node(frontNode.x+2,frontNode.y+1));
dp[frontNode.x+2][frontNode.y+1] = Math.min(dp[frontNode.x+2][frontNode.y+1],dp[frontNode.x][frontNode.y]+1);
}
if(frontNode.x+1<11&&frontNode.y+2<10&&visited[frontNode.x+1][frontNode.y+2]==false){
//右下2
visited[frontNode.x+1][frontNode.y+2] = true;
queue.add(new Node(frontNode.x+1,frontNode.y+2));
dp[frontNode.x+1][frontNode.y+2] = Math.min(dp[frontNode.x+1][frontNode.y+2],dp[frontNode.x][frontNode.y]+1);
}
}
if(dp[x2][y2]==65535){
System.out.println(0);
}else{
System.out.println(dp[x2][y2]);
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(true){
Main Horse = new Main();
int x1 = in.nextInt();
int y1 = in.nextInt();
int x2 = in.nextInt();
int y2 = in.nextInt();
if(x1==0&&y1==0&&x2==0&&y2==0){
break;
}
Horse.BFS(x1,y1,x2,y2);
}
}
}