岩浆地牢

本文主要是介绍岩浆地牢，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

两个人在地牢中移动，问他们相遇的最少步数。一个人移动时另一个人也会移动，不能移动到岩浆上，碰到岩石则不动。

广度优先搜索。

#include<cstdio>
#include<string.h>
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
int n,m,ans;
struct point
{int x,y;
};point paris,helen;
point queue[160000][2];
int step[20][20][20][20];
int map[20][20],mv[4];void init()
{scanf("%d%d\n",&n,&m);memset(map,0,sizeof(map));char st[100];int i,j;for(int i=0;i<n;i++){gets(st);for(j=0;j<strlen(st);j++)if(st[j]=='#')map[i][j]=1;else if(st[j]=='!')map[i][j]=2;else if(st[j]=='P'){paris.x=i;paris.y=j;}else if(st[j]=='H'){helen.x=i;helen.y=j;}}gets(st);for(i=0;i<4;i++)switch(st[i]){case 'N':mv[i]=0;break;case 'S':mv[i]=1;break;case 'W':mv[i]=2;break;case 'E':mv[i]=3;}}int bfs_search(){if(paris.x==helen.x&&paris.y==helen.y)return 0;int head,tail,now,i,xp,yp,xh,yh;memset(step,0xff,sizeof(step));queue[0][0].x=paris.x;queue[0][0].y=paris.y;queue[0][1].x=helen.x;queue[0][1].y=helen.y;step[paris.x][paris.y][helen.x][helen.y]=0;head=-1;tail=0;while(head++<tail){now=step[queue[head][0].x][queue[head][0].y][queue[head][1].x][queue[head][1].y];if(now==255)return -1;for(i=0;i<4;i++){xp=queue[head][0].x+dir[i][0];yp=queue[head][0].y+dir[i][1];xh=queue[head][1].x+dir[mv[i]][0];yh=queue[head][1].y+dir[mv[i]][1];if(xp>=n||xp<0 || yp>=m || yp<0 || xh>=n ||xh<0||yh>=m||yh<0)continue;if(map[xp][yp]>=1||map[xh][yh]==2)continue;if(map[xh][yh]){xh=queue[head][1].x;yh=queue[head][1].y;}if(step[xp][yp][xh][yh]==-1){tail++;queue[tail][0].x=xp;queue[tail][0].y=yp;queue[tail][1].x=xh;queue[tail][1].y=yh;step[xp][yp][xh][yh]=now+1;if(xp==xh&&yp==yh)return now+1;if(xp==queue[head][1].x&&yp==queue[head][1].y&&xh==queue[head][0].x&&yh==queue[head][0].y)return now+1;}}}return -1;}int main(){init();ans=bfs_search();if(ans>=0)printf("%d\n",ans);else printf("Impossible\n");return 0;}

这篇关于岩浆地牢的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---