CTU 2012 Gregory the Grasshopper (BFS)
题目链接: .html
题目大意: 求从一个点到底另一个点的最短时间
但是走的路径不是相邻的格子，而是像中国象棋马的走法走“日”字
单位时间只能走一次，求最短时间是多少？
走的过程中不可超过边界范围
解题思路： 这道题其实跟 poj 2234 Knight Moves 的思路一样
从原点开始广搜，每次搜八个位置
如图（像象棋的马走日字）
每走一个步，下一步的步数等于上一步加1，走到终点则立刻退出
走到那个点，会把这个点周围八个位置可以走的地方都走一次
下次没必要再走这个点，就算走回来可以走的地方上次肯定已经走过了
所以此题没必要用SPFA
这道题也可以用双向BFS，但是我之前做过大量测试，对于这种最短路问题双向BFS效果很不明显！
代码:
#include <stdio.h>
#include <stdio.h>
#include <string.h>
#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;
}注：原创文章，转载请注明出处
CTU 2012 Gregory the Grasshopper (BFS)
题目链接: .html
题目大意: 求从一个点到底另一个点的最短时间
但是走的路径不是相邻的格子，而是像中国象棋马的走法走“日”字
单位时间只能走一次，求最短时间是多少？
走的过程中不可超过边界范围
解题思路： 这道题其实跟 poj 2234 Knight Moves 的思路一样
从原点开始广搜，每次搜八个位置
如图（像象棋的马走日字）
每走一个步，下一步的步数等于上一步加1，走到终点则立刻退出
走到那个点，会把这个点周围八个位置可以走的地方都走一次
下次没必要再走这个点，就算走回来可以走的地方上次肯定已经走过了
所以此题没必要用SPFA
这道题也可以用双向BFS，但是我之前做过大量测试，对于这种最短路问题双向BFS效果很不明显！
代码:
#include <stdio.h>
#include <stdio.h>
#include <string.h>
#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;
}注：原创文章，转载请注明出处
发布评论