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
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.
Output
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.
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)，由于这题数据规模较大，因此我用的是双向(BFS)。所谓双向(BFS)，它的原理是起点和终点同时扩展节点，当遇到相同的节点时，记录答案退出。双向(BFS)减少了节点的扩展，效率比普通的(BFS)高出几倍，且内存开销小。
双向(BFS)的优化
双向(BFS)效率是惊人的，如果运用的好，效率将会更高
让我们来分析一下，当出现一边节点特别多时，扩展节点多的一边会使节点数成指数倍增长，最终导致效率退化到单向(BFS)，所以我的程序还可以用一个(if)语句，使两个(BFS)中的节点尽量平衡。
PS：其实这题并不需要这样判断，数据规模和节点的扩展都使得两边会差不多平衡。但这也不失是一种好的优化技巧。
(if)语句的代码片段
if(!Q1.empty()&&Q1.size()<=Q2.size())//仅有此处需改
{
处理
}
if(!Q2.empty())
{
处理
}
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=310,FQ[8][2]={{1,2},{2,1},{-1,2},{2,-1},{-2,1},{1,-2},{-1,-2},{-2,-1}};
int n,x1,y1,x2,y2,f[N][N],step[N][N];
typedef pair<int,int> pr;
queue<pr> Q1,Q2;
bool Check(int x,int y)
{
if(x<1||y<1||x>n||y>n) return 0;
return 1;
}
void Bfs()
{
while(!Q1.empty()) Q1.pop();
while(!Q2.empty()) Q2.pop();
Q1.push(make_pair(x1,y1)),Q2.push(make_pair(x2,y2));
pr top,next;
while((!Q1.empty())||(!Q2.empty()))
{
if(!Q1.empty())
{
top=Q1.front(); Q1.pop();
if(top.first==x2&&top.second==y2)
{
printf("%d
",step[top.first][top.second]);
return;
}
for(int i=0;i<=7;++i)
{
next.first=top.first+FQ[i][0],
next.second=top.second+FQ[i][1];
if(Check(next.first,next.second))
{
if(!f[next.first][next.second])
{
f[next.first][next.second]=1,
step[next.first][next.second]=step[top.first][top.second]+1,
Q1.push(next);
}
else if(f[next.first][next.second]==2)
{
printf("%d
",
step[top.first][top.second]+1+step[next.first][next.second]);
return;
}
}
}
}
if(!Q2.empty())
{
top=Q2.front(); Q2.pop();
if(top.first==x1&&top.second==y1)
{
printf("%d
",step[top.first][top.second]);
return;
}
for(int i=0;i<=7;++i)
{
next.first=top.first+FQ[i][0],
next.second=top.second+FQ[i][1];
if(Check(next.first,next.second))
{
if(!f[next.first][next.second])
{
f[next.first][next.second]=2,
step[next.first][next.second]=step[top.first][top.second]+1,
Q2.push(next);
}
else if(f[next.first][next.second]==1)
{
printf("%d
",
step[top.first][top.second]+1+step[next.first][next.second]);
return;
}
}
}
}
}
}
int main()
{
int T;
for(scanf("%d",&T);T;--T)
{
memset(f,0,sizeof(f)),memset(step,0,sizeof(step));
scanf("%d%d%d%d%d",&n,&x1,&y1,&x2,&y2);
++x1,++y1,++x2,++y2,
step[x1][y1]=step[x2][y2]=0,
f[x1][y1]=1,f[x2][y2]=2;
Bfs();
}
return 0;
}