题目大意：国际象棋给你一个起点和一个终点，按骑士的走法，从起点到终点的最少移动多少次。
求最少明显用bfs，下面给出三种搜索算法程序：
// BFS
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=;
int r1,c1,r2,c2;
struct Node
{
int r,c;
Node(int r,int c):r(r),c(c){}
};
int vis[maxn][maxn];
int dist[maxn][maxn];
queue<Node> Q;
int dr[]={-,-,-,-,,,,};
int dc[]={-,,,-,,-,,-};
int BFS()
{
if(r1==r2&&c1==c2) return ;
while(!Q.empty()) Q.pop();
memset(vis,,sizeof(vis));
vis[r1][c1]=;
dist[r1][c1]=;
Q.push(Node(r1,c1));
while(!Q.empty())
{
Node node=Q.front();Q.pop();
int r=node.r,c=node.c;
for(int d=;d<;d++)
{
int nr=r+dr[d];
int nc=c+dc[d];
if(nr>=&&nr< && nc>= &&nc< &&vis[nr][nc]==)
{
if(nr==r2&&nc==c2) return dist[r][c]+;
dist[nr][nc]=+dist[r][c];
Q.push(Node(nr,nc));
vis[nr][nc]=;
}
}
}
return -;
}
int main()
{
char str1[],str2[];
while(scanf("%s%s",str1,str2)==)
{
r1=str1[]-'';
c1=str1[]-'a';
r2=str2[]-'';
c2=str2[]-'a';
printf("To get from %s to %s takes %d knight moves.\n",str1,str2,BFS());
}
return ;
}
DFS：
注意visited结点，如果步数较小也继续搜索
// DFS
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=;
int r1,c1,r2,c2;
struct Node
{
int r,c;
Node(int r,int c):r(r),c(c){}
};
int vis[maxn][maxn];
int dist[maxn][maxn];
int dr[]={-,-,-,-,,,,};
int dc[]={-,,,-,,-,,-};
int ans;//最终答案
void DFS(int r,int c,int len)
{
if(ans<=len || r< || r>= || c< || c>=) return ;//剪枝
if(r==r2&&c==c2) ans=min(ans,len);
if(vis[r][c]== || dist[r][c]>len)
{
vis[r][c]=;
dist[r][c]=len;
}
else if(vis[r][c]== && len >= dist[r][c] )
return ;
for(int d=;d<;d++)
{
int nr=r+dr[d];
int nc=c+dc[d];
DFS(nr,nc,len+);
}
}
int main()
{
char str1[],str2[];
while(scanf("%s%s",str1,str2)==)
{
r1=str1[]-'';
c1=str1[]-'a';
r2=str2[]-'';
c2=str2[]-'a';
memset(vis,,sizeof(vis));
ans=;
DFS(r1,c1,);
printf("To get from %s to %s takes %d knight moves.\n",str1,str2,ans);
}
return ;
}
A*算法：
g函数为沿路径从起点到当前点的移动耗费(经过的步数)，启发函数h为当前格子到终点横坐标差与纵坐标差的和(曼哈顿距离)，用优先队列保存每个状态按照g+h排序。通常，我们令水平或者垂直移动的耗费为10，对角线方向耗费为14。取这些值是因为沿对角线的距离是沿水平或垂直移动耗费的的根号2，或者约1.414倍。为了简化，可以用10和14近似。
bfs
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio> using namespace std; const int maxn = ; struct Node{
int x,y,step;
int f,g,h;
// g函数为走到当前状态的经过的步数，启发函数h为当前格子到终点横坐标差与纵坐标差的和，用优先队列保存每个状态按照g+h排序
bool operator < (const Node & tmp) const{
return f > tmp.f;
}
}node; bool visd[maxn][maxn];
priority_queue<Node> Que;
int dirs[][]={{-,-},{-,},{,-},{,},{-,-},{-,},{,-},{,}};
int start_x,start_y,end_x,end_y,ans; bool isIN(int x,int y)
{
if(x>=||x<)return false;
if(y>=||y<)return false;
return true;
}
void init()
{
memset(visd,false,sizeof(visd));
while(!Que.empty())Que.pop();
Node S;
S.x=start_x;S.y=start_y;
S.step=;S.g=;S.h=(abs(end_x-start_x)+abs(end_y-start_y))*;
S.f=S.g+S.h;
visd[S.x][S.y]=true;
Que.push(S);
ans=-;
} void Astar()
{
Node A,B;
while(!Que.empty())
{
A=Que.top();Que.pop();
if(A.x==end_x&&A.y==end_y)
{
ans=A.step;
break;
}
for(int i=;i<;i++)
{
int xx=dirs[i][]+A.x;
int yy=dirs[i][]+A.y;
if(isIN(xx,yy)==false||visd[xx][yy])continue;
B.x=xx;B.y=yy;
B.step=A.step+;
B.g=A.g+;
B.h=(abs(end_y-yy)+abs(end_x-xx))*;
B.f=B.g+B.h;
visd[B.x][B.y]=true;
Que.push(B);
}
}
} int main()
{
char line[];
while(gets(line))
{
start_x=line[]-'a';start_y=line[]-'';
end_x=line[]-'a';end_y=line[]-'';
init();
Astar();
printf("To get from %c%c to %c%c takes %d knight moves.\n",line[],line[],line[],line[],ans);
} return ;
}
