题目描述
当WJ醒来时,发现自己被困在一个地图的左上角,幸好WJ有张图,并了解到出口正是迷宫的右下角,至少有一条路径可以到达出口。
整个地图有些地方会有障碍(保证左上角右下角没有),WJ可以快速奔跑,只是需要拐弯时令人很不爽。为了保持心情愉悦,WJ想知道最少需要几次转弯。
输入
第一行两个数r,c表示地图大小
接下来r行,每行c个字符,‘*’代表此处有障碍,‘0’代表空地。
输出
一个数,表示最少需要几次转弯。数据保证有解。
输入样例
2 5
0*000
000*0
输出样例
4
说明
【数据范围】
对于20%的数据,r、c≤10;
对于40%的数据,r、c≤100;
对于100%的数据,r、c≤500。
思路
BFS
从(1,1)到(n,m),从没有转弯到右转弯
从(1,1)开始,先往一个方向跑,没走一个放入队列,直到跑到墙
然后从队列里拿一个来往另外两边跑,直到跑到墙
然后到达(n,m)输出拐弯数
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define INF 1e9
using namespace std;
const int dx[5]={0,1,0,-1,0};
const int dy[5]={0,0,1,0,-1};
int flag[505][505],f[505][505];
//flag[i][j]=0代表(i,j)没有走过
//flag[i][j]=1代表(i,j)有障碍
//flag[i][j]=2代表(i,j)走过了
int n,m,t,ans=INF;
char c;
bool check(int x,int y)
{
if(x<1 || x>n || y<1 || y>m)return 0;
if(flag[x][y]==1)return 0;
return 1;
}
void bfs()
{
queue<int>x;x.push(1);
queue<int>y;y.push(1);//从(1,1)开始
queue<int>z;z.push(-1);
flag[1][1]=2;
while(z.size())
{
int xx=x.front();x.pop();
int yy=y.front();y.pop();
int zz=z.front();z.pop();
for(int i=1;i<=4;++i)//四个方向
{
int k=1;
while(check(xx+dx[i]*k,yy+dy[i]*k))//朝一个方向一直跑
{
int l=xx+dx[i]*k;
int r=yy+dy[i]*k;
++k;
if(!flag[l][r])//判断是否走过或障碍物
{
if(l==n && r==m)
{
printf("%d",zz+1);
return;
}
x.push(l);
y.push(r);
z.push(zz+1);
flag[l][r]=2;//记录
}
}
}
}
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
getchar();
for(int j=1;j<=m;++j)
{
c=getchar();
flag[i][j]=(c=='*'?1:0);
}
}
bfs();
return 0;
}