题目连接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1657
版本一：
1，用广搜求王的最小步数，这里出了一些问题：在元素入队时不设置被访标志，而是在出队时才设置被访标志，这就存在问题了，因为一个标志可能被队列中多个相邻的节点同时发现这样就会时同一个元素多次入队，被多次访问；看了一下算导上的思想，发现了这个错误，算导上将每个节点的被访程度分为未发现、发现、已访问，进入队列的只能是未发现态。所以一个节点只要被发现就应该设置标志，不能再加入队列了。
2，象不能一步达到时的走法只能有两种情况：
M 或者 A B
A B M
容易推出来A和B应该满足的条件
3，还要处理好源点和终点相同的特殊情况。
#include <iostream>
using namespace std;
struct Point
{
int r;
int c;
int step;
};
int t,r1,r2,r3,r4;
char r,c;
Point org,des;
Point q[64];
int hd,tl;
bool visit[8][8];
void BFS()
{
memset(visit,false,sizeof(visit));
hd = tl = 0;
org.step = 0;
q[tl++] = org;
visit[org.r][org.c] = true;
int i;
Point cur,next;
int offset[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{1,-1},{-1,1},{1,1},{-1,-1}};
while(hd != tl)
{
cur = q[hd++];
// visit[cur.r][cur.c] = true;
for(i = 0;i < 8;++i)
{
next.r = cur.r + offset[i][0];
next.c = cur.c + offset[i][1];
if(next.r >= 0 && next.r < 8 && next.c >= 0 && next.c < 8 &&
!visit[next.r][next.c])
{
next.step = cur.step + 1;
q[tl++] = next;
visit[next.r][next.c] = true;
if(next.r == des.r && next.c == des.c)
break;
}
}
if(next.r == des.r && next.c == des.c)
{
des.step = next.step;
break;
}
}
}
int main()
{
freopen("in.txt","r",stdin);
cin >> t;
while(t--)
{
cin >> c >> r;
org.r = r - '1';
org.c = 7 + 'a' - c;
cin >> c >> r;
des.r = r - '1';
des.c = 7 + 'a' - c;
if(des.r == org.r && des.c == org.c)
{
cout << 0 << ' ' << 0 << ' ' << 0 << ' ' << 0 << endl;
continue;
}
BFS();
cout << des.step << ' ';
if(abs(des.r-org.r) == abs(des.c - org.c) || des.r == org.r || des.c == org.c)
cout << 1 << ' ';
else
cout << 2 << ' ';
if(des.r == org.r || des.c == org.c)
cout << 1 << ' ';
else
cout << 2 << ' ';
if(abs(des.r-org.r) == abs(des.c - org.c))
cout << 1 << endl;
else if((abs(des.r-org.r) + abs(des.c - org.c)) % 2 == 0)
cout << 2 << endl;
else
cout << "Inf" << endl;
}
return 0;
}
版本二：各种棋子步数都可以通过公式计算出来，王的也不例外！
#include <iostream>
using namespace std;
int main()
{
freopen("in.txt","r",stdin);
int t,x,y,o1,o2,o3,o4;
char c1,r1,c2,r2;
cin >> t;
while(t--)
{
cin >> c1 >> r1 >> c2 >> r2;
if(r1 == r2 && c1 == c2)
{
printf("0 0 0 0/n");
continue;
}
x = abs(c1-c2);
y = abs(r1-r2);
o1 = x > y ? x : y;
if(x == y || r1 == r2 || c1 == c2)
o2 = 1;
else
o2 = 2;
if(r1 == r2 || c1 == c2)
o3 = 1;
else
o3 = 2;
if(x == y)
o4 = 1;
else if((x+y) % 2 == 0)
o4 = 2;
else
o4 = -1;
if(o4 == -1)
printf("%d %d %d %s/n",o1,o2,o3,"Inf");
else
printf("%d %d %d %d/n",o1,o2,o3,o4);
}
return 0;
}