2013
11-10

# Knight Moves

Background

Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?

The Problem

Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.

For people not familiar with chess, the possible knight moves are shown in Figure 1.

The input begins with the number n of scenarios on a single line by itself.

Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4 <= l <= 300). The entire board has size l * l. The second and third line contain pair of integers {0, ..., l-1}*{0, ..., l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario.

For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line.

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

5
28
0

import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {

private static int[][] directions = new int[][]{
{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};

static void BreadthFirstSearch(int startX, int startY,
chessNode[][] chessPanel, int size) {
chessNode currentNode = null, nextNode = null;
currentNode = chessPanel[startY][startY] =
new chessNode(startX, startY, true, 0, false);
while (!queue.isEmpty()) {
currentNode = queue.removeFirst();
if (currentNode.isTarget()) {
break;
}
for (int i = 0; i < 8; i++) {
int x = currentNode.getX() + directions[i][0];
int y = currentNode.getY() + directions[i][1];
int step = currentNode.getStep();
if (x >= 0 && x < size && y >= 0 && y < size) {
if (chessPanel[x][y] == null) {
chessPanel[x][y] = new chessNode(x, y, false, 0, false);
}
nextNode = chessPanel[x][y];
if (!nextNode.isVisited()) {
nextNode.setVisited(true);
nextNode.setStep(step + 1);
}
}
}
}
}

public static void main(String[] args) {
int n = 0;
int size = 0;
int startX = 0, startY = 0, endX = 0, endY = 0;
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
n = scanner.nextInt();
for (int i = 0; i < n; i++) {
size = scanner.nextInt();
startX = scanner.nextInt();
startY = scanner.nextInt();
endX = scanner.nextInt();
endY = scanner.nextInt();
chessNode[][] chessPanel = new chessNode[size][size];
chessPanel[endX][endY] = new chessNode(endX, endY, false, 0, true);
System.out.println(chessPanel[endX][endY].getStep());
}
}
}

class chessNode {

private int x;
private int y;
private boolean visited;
private int step;

public int getX() {
return x;
}

public chessNode(int x, int y, boolean visited, int step, boolean target) {
this.x = x;
this.y = y;
this.visited = visited;
this.step = step;
this.target = target;
}

public void setX(int x) {
this.x = x;
}

public int getY() {
return y;
}

public void setY(int y) {
this.y = y;
}
private boolean target;

public boolean isVisited() {
return visited;
}

public void setVisited(boolean visited) {
this.visited = visited;
}

public int getStep() {
return step;
}

public void setStep(int step) {
this.step = step;
}

public boolean isTarget() {
return target;
}

public void setTarget(boolean target) {
this.target = target;
}
}

1. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！

2. 博主您好，这是一个内容十分优秀的博客，而且界面也非常漂亮。但是为什么博客的响应速度这么慢，虽然博客的主机在国外，但是我开启VPN还是经常响应很久，再者打开某些页面经常会出现数据库连接出错的提示