#include<iostream> #include<cstdio> #include<stdio.h> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int MAXN=55; const int dx[4]={-1,0,1,0}; const int dy[4]={0,1,0,-1}; struct Cnode{ int x,y,d,s; }p; bool vis[MAXN][MAXN][4]; bool map[MAXN][MAXN]; int n,m; int sx,sy,ex,ey,sd; queue<Cnode> q; inline void Init(){ char ch; memset(map,true,sizeof(map)); scanf("%d%d",&n,&m); for(register int i=1;i<=n;i++) for(register int j=1;j<=m;j++){ int r; scanf("%d",&r); if(r)//一个格子有障碍,周围4个点都不能走 map[i-1][j-1]=map[i][j-1]=map[i-1][j]=map[i][j]=false; } scanf("%d%d%d%d %c",&sx,&sy,&ex,&ey,&ch); if(!map[sx][sy]||!map[ex][ey]){ printf("-1\n"); exit(0); } ch=tolower(ch); if(ch==‘n‘) sd=0; else if(ch==‘e‘) sd=1; else if(ch==‘s‘) sd=2; else sd=3; p.x=sx;p.y=sy;p.d=sd;p.s=0; q.push(p); } int main(){ Init();//初始化 int xx,yy,fx,fy,fd,fs;//注意在搜索里开变量第9和第10个点可能会MLE while(!q.empty()){//广搜 fx=q.front().x,fy=q.front().y,fd=q.front().d,fs=q.front().s; q.pop(); if(fx==ex&&fy==ey){ printf("%d\n",fs);//找到了就直接输出结束 return 0; } if(vis[fx][fy][fd]) continue; vis[fx][fy][fd]=true; p.x=fx;p.y=fy;p.d=(fd+1)%4;p.s=fs+1; q.push(p);//右转 p.x=fx;p.y=fy;p.d=(fd+3)%4;p.s=fs+1; q.push(p);//左转 for(register int i=1;i<=3;i++){//前进1步到3步 xx=fx+i*dx[fd]; yy=fy+i*dy[fd]; if(xx<=0||xx>=n||yy<=0||yy>=m||!map[xx][yy]) break; p.x=xx;p.y=yy;p.d=fd;p.s=fs+1; q.push(p); } } printf("-1\n"); return 0; }
原文:https://www.cnblogs.com/MLETNxtl/p/11809487.html