[UVA][bfs] 10477 - The Hybrid Knight
The Hybrid Knight
| The Hybrid Knight |
Hybridization is a very important concept in Biology, Chemistry and in many other fields. But is not at all an important concept in chess. Today we shall introduce a new chess knight, which can move like a normal knight, a mutant knight and like a mutant pawn in a chessboard.
The following figure illustrates the different types of moves of our hybrid knight. Please note that the knight is never allowed to land outside the board.
Unfortunately, the knight cannot move according to his own will. It maintains the following cyclic order when it chooses its movement. It means if the knight's first movement is like a knight, the second movement will be like a mutant knight, the third movement will be like a mutant pawn, the fourth movement will be again like a knight and so on. The same cycle applies if the hybrid knight starts with the mutant knight move or with the mutant pawn move. The cycle to be followed is shown in the given figure.
Given the size of the square shaped board, your job is to find the minimum number of moves required by the hybrid knight to reach from one board position to another. The board positions are numbered in row major order from top to bottom. So in a (8×8) chessboard the identifier of the top-left corner is 1 and the identifier of the bottom right corner is 64.
Input
The input file contains at most 20 sets of input. Each set starts with two integers N( 4
N20)
and S(
S1000). N indicates that you have to work with a
N×N board and S is the total
number of queries in that set. Each of the next S lines contains 1 query. Each query contains two
integers B and E (
1B, EN*N). Here B is the starting location of the knight and E is the
destination location of the knight. Input is terminated with a set whose value of N is zero. This
case should not be processed. You can assume that the hybrid knight takes 0 moves to go from
X to X, where X is a valid board position. However, there will be no such query where B and E
is equal.
Output
For each set of input you should output the serial of the set as shown in the output for sample input. For each query in a set you should output the minimum number of moves required by the hybrid knight to move from B to E. If the destination is unreachable from the source, print a `?' without the quotes.
Sample Input
5 2 10 15 10 20 10 1 2 10 0 10
Sample Output
Set 1: 1 2 Set 2: 4
Note: The illustration given below shows the movement required for set 2.
Here to go from 2 to 10 in a
10×10 board the hybrid knight uses its mutant knight move first to go to cell number 15.
Then it uses the mutant pawn move to go one row down to cell number 25. The third move is like a
regular knight, it takes our knight to cell number 17. The fourth and final move is a mutant
knight move that takes our knight to the destination. We're showing the first 4 rows of the
10×10 board here.
Problem-setters: Monirul Hasan Tomal (Implementation & Enhancement) & Shahriar Manzoor (Basic Idea & Initial Problem Statement)
題目描述：
有三種騎士走法，按照順序改變下一次的走法，而在最後一步又可以以特別的斜走抵達目的地。
一開始並沒有限制以哪一種走法開頭。
求從起點到終點的最短步數。
題目解法：
bfs
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int dist[25][25][3];
int dx1[] = {0, 0, 1, -1};
int dy1[] = {1, -1, 0, 0};
int dx2[] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy2[] = {2, -2, 2, -2, 1, -1, 1, -1};
int dx3[] = {1, 1, -1, -1, 3, 3, -3, -3};
int dy3[] = {3, -3, 3, -3, 1, -1, 1, -1};
int dxs[] = {1, 1, -1, -1};
int dys[] = {1, -1, 1, -1};
void bfs(int sx, int sy, int ex, int ey, int n) {
queue<int> X, Y, K;
int tx, ty, sk;
X.push(sx), Y.push(sy), K.push(0);
X.push(sx), Y.push(sy), K.push(1);
X.push(sx), Y.push(sy), K.push(2);
memset(dist, 0, sizeof(dist));
dist[sx][sy][0] = dist[sx][sy][1] = dist[sx][sy][2] = 0;
while(!X.empty()) {
sx = X.front(), sy = Y.front(), sk = K.front();
int sd = dist[sx][sy][sk];
if(sx == ex && sy == ey) {
printf("%d\n", sd);
return;
}
X.pop(), Y.pop(), K.pop();
//printf("%d %d %d\n", sx, sy, sk);
sk = (sk+1)%3;
for(int i = 0; i < 4; i++) {
tx = sx + dxs[i], ty = sy + dys[i];
if(tx < 0 || ty < 0 || tx >= n || ty >= n)
continue;
if(tx == ex && ty == ey && dist[tx][ty][0] == 0) {
dist[tx][ty][0] = sd+1;
X.push(tx), Y.push(ty), K.push(0);
}
}
if(sk == 0) {
for(int i = 0; i < 4; i++) {
tx = sx + dx1[i], ty = sy + dy1[i];
if(tx < 0 || ty < 0 || tx >= n || ty >= n)
continue;
if(dist[tx][ty][0] == 0) {
dist[tx][ty][0] = sd+1;
X.push(tx), Y.push(ty), K.push(0);
}
}
}
if(sk == 1) {
for(int i = 0; i < 8; i++) {
tx = sx + dx2[i], ty = sy + dy2[i];
if(tx < 0 || ty < 0 || tx >= n || ty >= n)
continue;
if(dist[tx][ty][1] == 0) {
dist[tx][ty][1] = sd+1;
X.push(tx), Y.push(ty), K.push(1);
}
}
}
if(sk == 2) {
for(int i = 0; i < 8; i++) {
tx = sx + dx3[i], ty = sy + dy3[i];
if(tx < 0 || ty < 0 || tx >= n || ty >= n)
continue;
if(dist[tx][ty][2] == 0) {
dist[tx][ty][2] = sd+1;
X.push(tx), Y.push(ty), K.push(2);
}
}
}
}
puts("?");
}
int main() {
int cases = 0;
int n, m, B, E;
while(scanf("%d %d", &n, &m) == 2 && n) {
printf("Set %d:\n", ++cases);
while(m--) {
scanf("%d %d", &B, &E);
B--, E--;
bfs(B/n, B%n, E/n, E%n, n);
}
}
return 0;
}