CTU 2012 Gregory the Grasshopper (BFS)

题目链接:

题目大意: 求从一个点到底另一个点的最短时间

但是走的路径不是相邻的格子，而是像中国象棋马的走法走“日”字

单位时间只能走一次，求最短时间是多少？

走的过程中不可超过边界范围

解题思路： 这道题其实跟 poj 2234 Moves 的思路一样

从原点开始广搜，每次搜八个位置

如图（像象棋的马走日字）

每走一个步，下一步的步数等于上一步加1，走到终点则立刻退出

走到那个点，会把这个点周围八个位置可以走的地方都走一次

下次没必要再走这个点，就算走回来可以走的地方上次肯定已经走过了

所以此题没必要用SPFA

这道题也可以用双向BFS，但是我之前做过大量测试，对于这种最短路问题双向BFS效果很不明显！

代码:

#include 
#include 
#include 
#define MAX 101
int n,m,edge[MAX][MAX];
typedef struct node{int x;int y;
}snode;
snode fx[8]={{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2}},list[MAX*MAX];int BFS(int sx,int sy,int ex,int ey)
{int i,tempx,tempy,temp1x,temp1y,e,s;e=s=0;edge[sx][sy]=0;  //初始化list[s].x=sx;list[s++].y=sy;while(e!=s)      //队列不为空{tempx=list[e].x;     //出队tempy=list[e++].y;for(i=0;i<8;i++)     //八个方向{temp1x=tempx+fx[i].x;temp1y=tempy+fx[i].y;if(temp1x==ex&&temp1y==ey){edge[temp1x][temp1y]=edge[tempx][tempy]+1;return edge[temp1x][temp1y];}if(temp1x>=1&&temp1x<=n&&temp1y>=1&&temp1y<=m&&edge[temp1x][temp1y]==-1){                //不超出范围，并且那个点没被访问过，则入队edge[temp1x][temp1y]=edge[tempx][tempy]+1;list[s].x=temp1x;list[s++].y=temp1y;}}}return -1;
}int main()
{int sx,sy,ex,ey;while(scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&ex,&ey)!=EOF){memset(edge,-1,sizeof(edge));if(sx==ex&&sy==ey)   //起点跟终点一样时直接打印 0 {printf("0\n");continue;}if(BFS(sx,sy,ex,ey)==-1)printf("impossible\n");elseprintf("%d\n",edge[ex][ey]);} return 0; 
}