题意
给你一个迷宫,要求输出靠左墙走,靠右墙走和最短的路径长度。
分析
最短的路径直接bfs就行了,就不多哔哔了。
因为题目保证S与E将始终位于迷宫边缘之一,而不是角落,所以我们可以确定他面朝的方向。
靠左墙走即先考虑他面朝方向的左边,如果不行,就顺时针遍历一下,找到最早的可行的方向。
而靠右墙走即先考虑他面朝方向的右边,如果不行,就逆时针遍历一下,找到最早的可行的方向。
举个栗子,一开始你要走左边,发现左边有墙,这时,我们应该优先考虑前面,这样才是靠左走。
每次走过来的方向即为面向的方向,再根据上述描述来做即可,方向搞对至关重要。
详细情况请见代码
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,m,T,d; char a[55][55]; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; //方向要按一定顺序,要么顺时针,要么逆时针 int vis[55][55]; struct obj{ int x,y; int tot; }q[2005]; void bfs(int x,int y){ //bfs求最短路 vis[x][y]=1; int head=1,tail=0; q[++tail].x=x; q[tail].y=y; q[tail].tot=1; while(head<=tail){ for(int i=0;i<4;i++){ int xx=q[head].x+dx[i]; int yy=q[head].y+dy[i]; if(a[xx][yy]=='#'||vis[xx][yy]||xx<=0||xx>n||yy<=0||yy>m) continue; q[++tail].x=xx; q[tail].y=yy; q[tail].tot=q[head].tot+1; vis[xx][yy]=1; if(a[xx][yy]=='E'){ printf("%d\n",q[tail].tot); return ; } } head++; } return ; } int dfsl(int x,int y,int dir,int cnt){ //靠左墙走 dir表示面朝方向 if(a[x][y]=='E') return cnt; int k=dir-1; if(k==0) k=4; for(int i=0;i<4;i++){ if(k==5) k=1; int xx=x+dx[k-1]; int yy=y+dy[k-1]; if(xx<=0||xx>n||yy<=0||yy>m||a[xx][yy]=='#'){ k++; //方向顺时针转 continue; } return dfsl(xx,yy,k,cnt+1); } } int dfsr(int x,int y,int dir,int cnt){ //靠右墙走 dir表示面朝方向 if(a[x][y]=='E') return cnt; int k=dir+1; if(k==5) k=1; for(int i=0;i<4;i++){ if(k==0) k=4; int xx=x+dx[k-1]; int yy=y+dy[k-1]; if(xx<=0||xx>n||yy<=0||yy>m||a[xx][yy]=='#'){ k--; //方向逆时针转 continue; } return dfsr(xx,yy,k,cnt+1); } } int main(){ scanf("%d",&T); while(T--){ memset(vis,0,sizeof(vis)); memset(q,0,sizeof(q)); scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%s",a[i]+1); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]=='S'){ if(i==n) d=1; else if(j==m) d=4; else if(i==1) d=3; else if(j==1) d=2; //分析面朝方向 1表示朝北,2表示朝东,3表示朝南,4表示朝西 printf("%d ",dfsl(i,j,d,1)); printf("%d ",dfsr(i,j,d,1)); bfs(i,j); } } } } return 0; }