会拐弯的眼睛

“那不是咱们的酒店‘风向标’么？”zjt刚出车站，就指着远处的一个楼说。旅途疲倦的大家瞬间又打起精神，准备赶紧到酒店休息。然而从车站出来的路途却是九曲十八弯，大家经历了无数的十字路口，绕来绕去，反复探索，才在一个角落的墙壁上看到了“风向标”三个字。 “你眼睛会拐弯，刚一出车站就能看到？”“就是你观测到了黑洞？”白浅抱怨连连。但是白浅并不是怨妇，她瞬间就出了一道题。给你一个n*m的地图，左上角记为(0，0)点，右下角记为(n-1,m-1)点。初始你在(startx，starty)点，想去(endx,endy)点，每一次你只能向上，下，左，右四个方向任选一个移动一步，不能穿越墙壁。请问你最少拐弯几次能够到达(endx,endy)点，如果无论如何都不能到达，输出-1。拐弯的定义：本次行动的方向与上次不同，则记为一次拐弯，第一步无论走哪个方向都不算拐弯。

输入第一行六个正整数 n，m 描述地图大小，startx, starty, endx, endy 描述起点，终点。
保证 $1 \leq n，m \leq 5000，0 \leq startx,endx \leq n-1, 0 \leq starty,endy \leq m-1$
接下来 n 行，每行一个长度为 m 的 01 串，0 代表可以走的空地，1 代表不能走的墙壁

#include<bits/stdc++.h> using namespace std; int sx,sy,n,m,ex,ey; char a[5010][5010]; int vis[5010][5010]; int dx[]={0, 1, 0, -1},dy[]={ 1, 0, -1, 0}; bool flag; struct Node { int x,y,c; }p; bool check(int x,int y) { if(x<0||x>=n||y<0||y>=m||vis[x][y]||a[x][y]=='1') return 0; //1 return 1; } void bfs() { queue<Node>q; q.push({sx,sy,0}); vis[sx][sy]=1; while(q.size()) { auto t=q.front(); q.pop(); for(int i=0;i<4;i++) { int tx=t.x,ty=t.y; while(1) { tx+=dx[i],ty+=dy[i]; if(tx==ex&&ty==ey) flag=1; if(!check(tx,ty)) break; vis[tx][ty]=t.c; q.push({tx,ty,t.c+1}); } } } return; } int main() { cin>>n>>m>>sx>>sy>>ex>>ey; for (int i=0;i<n;i++) scanf("%s",&a[i]); bfs(); if(flag) cout<<vis[ex][ey]<<endl; else puts("-1"); }

详情