A Chess Knight

Presumably everybody knows how a knight can move on a chessboard. One may agree that its movements are quite monotonous, so to make them more entertaining let's define a so called ``dynamic knight". A dynamic knight can perform many different movements that may belong to three types:

• type K: two fields forward (in any direction) and one sidewise - like ``regular knight";
• type B: two fields diagonally - more like a bishop;
• type T: sort of teleportation to a field which is a mirror reflection with respect to any of two axes of symmetry of the chessboard (we take into consideration only axes of symmetry parallel to sides of the chessboard);

The picture below shows all possible movements of a knight divided into three types K, B and T. Obviously our knight, like the ``regular" one cannot move outside the chessboard.

For a dynamic knight it is not relevant whether the fields between the starting field and ending one are occupied or not (again like for the ``regular knight"). It only matters whether the ending field is empty. Then the movement can be performed. There has to be a restriction among so many capabilities of a dynamic knight. It cannot perform the same sort of movements consecutively (just not to fall into routine).

Having redefined a chess knight, why not to redefine a chessboard? Our chessboard will be a square of size . N can be any integer number from the range of 3..20. There can be several obstacles of any shape on a chessboard so a knight cannot stop on these defected fields.

Your task is to write a program which can calculate the minimal number of movements to get the knight from one given field to another one. It may be assumed that the first movement can be of any type.

Input 

First line contains the number N, being the size of a chessboard. The second one contains field coordinates separated by space character, which is a knight current standpoint. Upper left-hand size corner has coordinates (1, 1). Third line contains destination field for the knight. Consecutive lines contain obstacle coordinates and the line with coordinates (0, 0) ends the obstacle description. Input can contain several sets of data.

Input's end is shown as a line defining chessboard's size as 0.

Output 

It is supposed to be fairly simple - one line with a single number being the calculated minimal number of movements.

Sample Input 

3
1 1
1 1
2 2
0 0
10
1 1
20 20
20 1
1 20
3 1
3 2
3 3
2 3
1 3
0 0
10
2 1
18 12
2 2
5 6
7 2
8 3
9 4
1 15
7 12
8 13
9 11
11 9
12 4
11 3
9 5
2 7
3 8
6 5
0 0
3
1 1
5 4
2 2
2 4
2 5
3 1
3 2
3 3
3 6
4 2
4 3
4 5
5 1
5 3
5 5
6 1
6 4
6 5
6 6
0 0
0

Sample Output 

Result : 0
Solution doesn't exist
Result : 6
Result : 4

---

Miguel A. Revilla
2000-01-10

題目描述：

動態騎士每次移動時都要更換移動模式，動態騎士有三種移動模式。

分別是一般在國際象棋中的騎士(走馬)、主教(走象)、以及鏡射走法。

題目解法：

BFS 即可，要特別注意不能連續做相同模式的移動。

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int sx, sy, ex, ey;
int x, y, n, i, j, k;
int g[50][50];
int dist[50][50][4];
queue<int> X, Y, K;
void typeK(int x, int y, int k) {
    int dx[] = {1,1,-1,-1,2,2,-2,-2};
    int dy[] = {2,-2,2,-2,1,-1,1,-1};
    int tx, ty;
    for(i = 0; i < 8; i++) {
        tx = x+dx[i], ty = y+dy[i];
        if(tx <= 0 || ty <= 0 || tx > n || ty > n)
            continue;
        if(g[tx][ty])
            continue;
        if(dist[tx][ty][0] == 0) {
            dist[tx][ty][0] = dist[x][y][k]+1;
            X.push(tx), Y.push(ty), K.push(0);
        }
    }
}
void typeB(int x, int y, int k) {
    int dx[] = {2,2,-2,-2};
    int dy[] = {2,-2,2,-2};
    int tx, ty;
    for(i = 0; i < 4; i++) {
        tx = x+dx[i], ty = y+dy[i];
        if(tx <= 0 || ty <= 0 || tx > n || ty > n)
            continue;
        if(g[tx][ty])
            continue;
        if(dist[tx][ty][1] == 0) {
            dist[tx][ty][1] = dist[x][y][k]+1;
            X.push(tx), Y.push(ty), K.push(1);
        }
    }
}
void typeT(int x, int y, int k) {
    int tx, ty;
    tx = n - x + 1, ty = y;
    if(g[tx][ty] == 0) {
        if(dist[tx][ty][2] == 0) {
            dist[tx][ty][2] = dist[x][y][k]+1;
            X.push(tx), Y.push(ty), K.push(2);
        }
    }   
    tx = x, ty = n - y + 1;
    if(g[tx][ty] == 0) {
        if(dist[tx][ty][2] == 0) {
            dist[tx][ty][2] = dist[x][y][k]+1;
            X.push(tx), Y.push(ty), K.push(2);
        }
    }
}
int bfs() {
    memset(dist, 0, sizeof(dist));
    if(sx == ex && sy == ey)
        return 0;
    for(i = 0; i < 3; i++) {
        X.push(sx), Y.push(sy), K.push(i);
    }
    while(!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        k = K.front(), K.pop();
        if(k != 0)
            typeK(x, y, k);
        if(k != 1)
            typeB(x, y, k);
        if(k != 2)
            typeT(x, y, k);
    }
    int ret = 0xfffffff;
    for(i = 0; i < 3; i++) {
        if(dist[ex][ey][i])
            ret = min(ret, dist[ex][ey][i]);
    }
    return ret;
}
int main() {
    while(scanf("%d", &n) == 1 && n) {
        scanf("%d %d", &sx, &sy);
        scanf("%d %d", &ex, &ey);
        memset(g, 0, sizeof(g));
        while(scanf("%d %d", &x, &y) == 2) {
            if(x == 0 && y == 0)
                break;
            g[x][y] = 1;
        }
        n *= 2;
        int ret = bfs();
        if(ret == 0xfffffff)
            puts("Solution doesn't exist");
        else
            printf("Result : %d\n", ret);
    }
    return 0;
}