BNU 26582Gregory the Grasshopper 搜索水题
Input /*D题 Gregory the Grasshopperhttp://acm.bnu.edu.cn/bnuoj/contest_show.php?cid=1405#problem/15734题意 一只青蛙可以跳到8个方向 和马走日的方向一样 输入map大小以及起点 终点问从起点到终点所需要的最小步骤思路： 简化版的马走日 还省去了蹩脚条件直接BFS+队列*/#include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> using namespace std; int step[10][2]={0,0,0,0,2,-1,2,1,1,2,-1,2,-2,-1,-2,1,1,-2,-1,-2},n,m; int p[5][2]={0,0,1,0,0,1,-1,0,0,-1}; int vis[200][200],ex,ey,flag,sx,sy,mm; struct haha { int x; int y; int step; //friend bool operator <(haha a,haha b) //{ // return a.step>b.step; //} }q,temp; void BFS() { int i,x,y,x1,y1; queue<haha>que; q.x=sx;q.y=sy;q.step=0; vis[sx][sy]=1; que.push(q); while(!que.empty()) { temp=que.front(); que.pop(); if(temp.x==ex&&temp.y==ey) { mm=temp.step;flag=1; return; } for(i=2;i<10;i++) { x=temp.x+step[i][0]; y=temp.y+step[i][1]; x1=temp.x+p[i/2][0]; y1=temp.y+p[i/2][1]; if(x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y]) { vis[x][y]=1; q.x=x; q.y=y; q.step=temp.step+1; que.push(q); } } } } int main(){ while(scanf("%d %d %d %d %d %d",&n,&m,&sx,&sy,&ex,&ey)!=EOF) { flag=0; memset(vis,0,sizeof(vis)); BFS(); if(flag) printf("%d\n",mm); else printf("impossible\n"); } return 0;}