οo怅惘ヤo ACM-ICPC HomePage

Description

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.

Input

Output

Sample Input

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

Sample Output

5
28
0

Source

TUD Programming Contest 2001, Darmstadt, Germany

【算法介绍】：BFS(Breadth – First Search)。

【题目描述】：第一行一个整数n,代表有n组测试数据。每组测试数据有3行,第一行为棋

盘的规模k,也就是(0...k-1)*(0...k-1)的棋盘,第二行是骑士的起始

位置(x1,y1),第3行市骑士的终点位置(x2,y2)。问：对于每组测试数据,

求出从起始位置到终点位置所跳的最少步数。

【题目分析】：广度优先搜索去搞就可以了。

#include <cstdio>
#include <cstring>

bool mark[300][300];
int sum[300][300];
//sum[i][j]计算起始位置到[i][j]的最少步数
int queue[90000][2];
int x[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int y[8] = {-2, -1, 1, 2, 2, 1, -1, -2};

void bfs(int p, int q, int l, int r, int k)
{
   int i;
   int tx, ty, px, py;
   int head = 0, tail = 1;
   queue[0][0] = p;
   queue[0][1] = q;
   mark[p][q] = true;
   sum[p][q] = 0;
   if (p == l && q == r) return;
   while (head < tail)
   {
      tx = queue[head][0];
      ty = queue[head][1];
      head++;
      for (i = 0; i < 8; i++)
      {
         px = tx + x[i];
         py = ty + y[i];
         if (px >= 0 && px < k && py >= 0 && py < k && (!mark[px][py]))
         {
            queue[tail][0] = px;
            queue[tail][1] = py;
            tail++;
            mark[px][py] = true;
            sum[px][py] = sum[tx][ty] + 1;
         }
      }
      if (px == l && py == r) break;
   }
}

int main()
{
   int n, i, k, x1, y1, x2, y2;
   scanf("%d",&n);
   for (i = 0; i < n; i++)
   {
      scanf("%d",&k);
      scanf("%d %d",&x1, &y1);
      scanf("%d %d",&x2, &y2);
      memset(mark,false,sizeof(mark));
      memset(sum,0,sizeof(sum));
      bfs(x1, y1, x2, y2, k);
      printf("%d\n",sum[x2][y2]);
   }
   return 0;
}