题目大意:给你一个迷宫,S是起点,E是终点,#是墙,.是路,S、E在迷宫的边界,并且有唯一解;求优先左转S到E的步数,优先右转S到E的步数,以及S到E的最短步数。
#include
#include
#include
#include
using namespace std;
struct point
{
int x,y,step;
};
char map[50][50];
queueq;
int n,m;
int lstep,rstep;
int go[4][2]={-1,0,0,-1,1,0,0,1};//四个方向,按左、前、右、后存储
int is_way(int x,int y)//判断此点是否可走
{
if(x<0 || x>=n || y<0 || y>=m || map[x][y]==‘#‘)
return 0;
return 1;
}
void ldfs(int x,int y,int dir)//左转优先,x,y记录当前位置,dir记录当前方向
{
lstep++;//步数
//cout<//getchar();
if(map[x][y]==‘E‘) return;//找到终点退出
if( is_way(x+go[(dir+1)%4][0],y+go[(dir+1)%4][1]) )//左转
ldfs( x+go[(dir+1)%4][0], y+go[(dir+1)%4][1], (dir+1)%4 );
else if( is_way(x+go[(dir)%4][0],y+go[(dir)%4][1]) )//前走
ldfs( x+go[(dir)%4][0], y+go[(dir)%4][1], (dir)%4 );
else if( is_way(x+go[(dir+3)%4][0],y+go[(dir+3)%4][1]) )//右转
ldfs( x+go[(dir+3)%4][0], y+go[(dir+3)%4][1], (dir+3)%4 );
else ldfs( x+go[(dir+2)%4][0], y+go[(dir+2)%4][1], (dir+2)%4 );//后退
}
void rdfs(int x,int y,int dir)//右转优先
{
rstep++;
if(map[x][y]==‘E‘) return;
if( is_way(x+go[(dir+3)%4][0],y+go[(dir+3)%4][1]) )//右转
rdfs( x+go[(dir+3)%4][0], y+go[(dir+3)%4][1], (dir+3)%4 );
else if( is_way(x+go[(dir)%4][0],y+go[(dir)%4][1]) )//前走
rdfs( x+go[(dir)%4][0], y+go[(dir)%4][1], (dir)%4 );
else if( is_way(x+go[(dir+1)%4][0],y+go[(dir+1)%4][1]) )//左转
rdfs( x+go[(dir+1)%4][0], y+go[(dir+1)%4][1], (dir+1)%4 );
else rdfs( x+go[(dir+2)%4][0], y+go[(dir+2)%4][1], (dir+2)%4 );//后退
}
int bfs()//求S到E最短距离,BFS模板即可
{
while(!q.empty())
{
point p=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=p.x+go[i][0];
int y=p.y+go[i][1];
if(map[x][y]==‘E‘) return p.step+1;
if(is_way(x,y))
{
point temp;
temp.x=x;
temp.y=y;
temp.step=p.step+1;
q.push(temp);
map[x][y]=‘#‘;
}
}
}
return 0;
}
int main()
{
int t;
cin>>t;
while(t--)
{
while(!q.empty())
q.pop();
int x,y;
cin>>m>>n;
for(int i=0;i)
for(int j=0;j)
{
cin>>map[i][j];
if(map[i][j]==‘S‘)
{
x=i;
y=j;
}
}
lstep=0;
rstep=0;
ldfs(x,y,0);
rdfs(x,y,0);
point p;
p.x=x;
p.y=y;
p.step=1;
q.push(p);
map[x][y]=‘#‘;
cout<‘ ‘<‘ ‘<endl;
}
return 0;
}