CTU 2012 Gregory the Grass hopper(BFS)
テーマリンク: http://contest.felk.cvut.cz/12prg/solved.html
タイトルの大意: 一つの点から最後までもう一つの点の最短時間を求めます.
しかし、歩く道は隣の格子ではなく、中国将棋の馬のように「日」の字を歩きます.
単位時間は一回しか歩けません.最短時間はいくらですか?
歩く過程で境界範囲を超えてはいけません.
問題解決の考え方: この問題はpoj 2234 Knight Movesと同じ考えです.
原点から広く検索し、毎回8つの位置を検索します.
図のように(将棋の馬が日本語を走るような)
一歩進むごとに、次のステップのステップ数は前のステップに1を加えることになります.終点まで行くとすぐに終了します.
その点に行くと、この点の周りの8つの場所を全部回ってみます.
今度はここを歩く必要がないです.歩いて帰ってもいいところは前回はきっと通り過ぎました.
だからこの問題はSPFAを使う必要がありません.
この問題は双方向BFSも使えますが、大量のテストをしたことがあります.このような最も短絡的な問題に対して、双方向BFSの効果はあまりはっきりしません.
コード:
タイトルの大意: 一つの点から最後までもう一つの点の最短時間を求めます.
しかし、歩く道は隣の格子ではなく、中国将棋の馬のように「日」の字を歩きます.
単位時間は一回しか歩けません.最短時間はいくらですか?
歩く過程で境界範囲を超えてはいけません.
問題解決の考え方: この問題はpoj 2234 Knight Movesと同じ考えです.
原点から広く検索し、毎回8つの位置を検索します.
図のように(将棋の馬が日本語を走るような)
一歩進むごとに、次のステップのステップ数は前のステップに1を加えることになります.終点まで行くとすぐに終了します.
その点に行くと、この点の周りの8つの場所を全部回ってみます.
今度はここを歩く必要がないです.歩いて帰ってもいいところは前回はきっと通り過ぎました.
だからこの問題は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
");
continue;
}
if(BFS(sx,sy,ex,ey)==-1)
printf("impossible
");
else
printf("%d
",edge[ex][ey]);
}
return 0;
}