“那不是咱们的酒店‘风向标’么？”zjt刚出车站，就指着远处的一个楼说。 旅途疲倦的大家瞬间又打起精神，准备赶紧到酒店休息。 然而从车站出来的路途却是九曲十八弯，大家经历了无数的十字路口，绕来绕去，反复探索，才在一个角落的墙壁上看到了“风向标”三个字。 “你眼睛会拐弯，刚一出车站就能看到？”“就是你观测到了黑洞？”白浅抱怨连连。但是白浅并不是怨妇，她瞬间就出了一道题。 给你一个n*m的地图，左上角记为(0，0)点，右下角记为(n−1,m−1))点。 初始你在(startx，starty)点，想去(endx,endy)点，每一次你只能向上，下，左，右四个方向任选一个移动一步，不能穿越墙壁。 请问你最少拐弯几次能够到达(endx,endy)点，如果无论如何都不能到达，输出-1。 拐弯的定义：本次行动的方向与上次不同，则记为一次拐弯，第一步无论走哪个方向都不算拐弯。
Input
输入第一行六个正整数 nn，mm 描述地图大小，startx,starty,endx,endy 描述起点，终点。
保证 1≤n，m≤5000，0≤startx,endx≤n−1,0≤starty,endy≤m−1
接下来 n 行，每行一个长度为 m 的 01 串，0 代表可以走的空地，1 代表不能走的墙壁
Output
输出一行一个正整数表示答案。
Samples
Input Copy
3 3 0 0 2 2 001 101 100
Output
2
题目大意：
就是问你从起点到终点最少拐几个弯
思路就是BFS，如果如果你拐弯之后，你要把它拐弯后的这个方向上的所有的点都标记上
#include<iostream> #include<algorithm> #include<queue> using namespace std; const int maxn=5e3+100; char a[maxn][maxn]; int vis[maxn][maxn]; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; struct node{ int x,y,t; }; int n,m,sx,sy,ex,ey; int ans=0x3f3f3f; int f=0; void BFS(){ queue<node>q; node tmp,nxt; tmp.x=sx,tmp.y=sy,tmp.t=-1;//因为第一步不算 vis[tmp.x][tmp.y]=1; q.push(tmp); while(!q.empty()){ tmp=q.front(); q.pop(); nxt.t=tmp.t+1; for(int i=0;i<4;i++){//相当于拐了一次弯 int xx=tmp.x,yy=tmp.y; while(1){//把这一个方向的都标记了 xx=xx+dx[i],yy=yy+dy[i]; if(xx<0||xx>=n||yy<0||yy>=m){ break; } if(a[xx][yy]=='1') break; if(vis[xx][yy]) break; vis[xx][yy]=1; nxt.x=xx,nxt.y=yy; if(xx==ex&&yy==ey){ f=1; ans=min(ans,nxt.t); return ; } q.push(nxt); } } } } int main(){ cin>>n>>m>>sx>>sy>>ex>>ey; for(int i=0;i<n;i++){ scanf("%s",a[i]); } BFS(); if(f){ cout<<ans<<endl; } else{ cout<<-1<<endl; } }