1781. KnightConstraints
Time Limit: 1 secs, Memory Limit: 64 MB
Description
Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another. The possible knight moves are shown in Figure 1.
Figure 1 Possible knight moves on the board
Input
The first line contains an integerT(≤10), indicating the number of test cases.
In every case, the first line contains an integerN(≤500), indicating the size of the chess board (the entire board has sizeN×N). The second and third line contain pair of integers (srcR, srcC), and (dstR, dstC), specifying the starting and ending position of the knight on the board (0 ≤ srcR, srcC, dstR, dstC ≤N– 1).
Output
For every case, output the minimum distance on a single line. If starting point and ending point are equal, distance is 0. If the knight can’t reach the ending point, distance is -1.
Sample Input210 00 0100 18 9Sample Output06
骑士巡游问题，，bfs：0.01s
#include <stdio.h>#include <queue>#include <string.h>using namespace std;int n;bool vis[505][505];struct point {int ii;int jj;};point sp, ep;int bfs() {if (sp.ii == ep.ii && sp.jj == ep.jj)return 0;queue<point> q;memset(vis, false, sizeof(vis));q.push(sp);point temp, temp_next;int step = 0;while (!q.empty()) {step++;int size = q.size();while (size–) {temp = q.front();q.pop();if (temp.ii > 1 && temp.jj < n – 1 && !vis[temp.ii – 2][temp.jj + 1]) {temp_next.ii = temp.ii – 2;temp_next.jj = temp.jj + 1;if (temp_next.ii == ep.ii && temp_next.jj == ep.jj) {return step;}vis[temp_next.ii][temp_next.jj] = true;q.push(temp_next);}if (temp.ii > 0 && temp.jj < n – 2 && !vis[temp.ii – 1][temp.jj + 2]) {temp_next.ii = temp.ii – 1;temp_next.jj = temp.jj + 2;if (temp_next.ii == ep.ii && temp_next.jj == ep.jj) {return step;}vis[temp_next.ii][temp_next.jj] = true;q.push(temp_next);}if (temp.ii < n – 1 && temp.jj < n – 2 && !vis[temp.ii + 1][temp.jj + 2]) {temp_next.ii = temp.ii + 1;temp_next.jj = temp.jj + 2;if (temp_next.ii == ep.ii && temp_next.jj == ep.jj) {return step;}vis[temp_next.ii][temp_next.jj] = true;q.push(temp_next);}if (temp.ii < n – 2 && temp.jj < n – 1 && !vis[temp.ii + 2][temp.jj + 1]) {temp_next.ii = temp.ii + 2;temp_next.jj = temp.jj + 1;if (temp_next.ii == ep.ii && temp_next.jj == ep.jj) {return step;}vis[temp_next.ii][temp_next.jj] = true;q.push(temp_next);}if (temp.ii < n – 2 && temp.jj > 0 && !vis[temp.ii + 2][temp.jj – 1]) {temp_next.ii = temp.ii + 2;temp_next.jj = temp.jj – 1;if (temp_next.ii == ep.ii && temp_next.jj == ep.jj) {return step;}vis[temp_next.ii][temp_next.jj] = true;q.push(temp_next);}if (temp.ii < n – 1 && temp.jj > 1 && !vis[temp.ii + 1][temp.jj – 2]) {temp_next.ii = temp.ii + 1;temp_next.jj = temp.jj – 2;if (temp_next.ii == ep.ii && temp_next.jj == ep.jj) {return step;}vis[temp_next.ii][temp_next.jj] = true;q.push(temp_next);}if (temp.ii > 0 && temp.jj > n – 1 && !vis[temp.ii – 1][temp.jj – 2]) {temp_next.ii = temp.ii – 1;temp_next.jj = temp.jj – 2;if (temp_next.ii == ep.ii && temp_next.jj == ep.jj) {return step;}vis[temp_next.ii][temp_next.jj] = true;q.push(temp_next);}if (temp.ii > 1 && temp.jj > 0 && !vis[temp.ii – 2][temp.jj – 1]) {temp_next.ii = temp.ii – 2;temp_next.jj = temp.jj – 1;if (temp_next.ii == ep.ii && temp_next.jj == ep.jj) {return step;}vis[temp_next.ii][temp_next.jj] = true;q.push(temp_next);}}}return -1;}int main() {int case_num;scanf("%d", &case_num);while (case_num–) {scanf("%d", &n);scanf("%d%d%d%d", &sp.ii, &sp.jj, &ep.ii, &ep.jj);printf("%d\n", bfs());}return 0;}
怪天怪地，我都不会怪你，你有选择幸福的权利…
