1757 - 最小转弯QAQ
给出一张地图，这张地图被分为n×m（n,m<=100）个
方块，任何一个方块不是平地就是高山。平地可以通过，高山则不能。现在你处在地图的（x1,y1）这块平地，问：你至少需要拐几个弯才能到达目的地
（x2,y2）？你只能沿着水平和垂直方向的平地上行进，拐弯次数就等于行进方向的改变（从水平到垂直或从垂直到水平）的次数。
例如：如图1，最少的拐弯次数为5。
【输入格式】第1 行：n m第2 至n+1行：整个地图地形描述（0：空地；1：高山），如（图1）第2 行地形描述为：1 0 0 0 0 1 0第3 行地形描述为：0 0 1 0 1 0 0……第n+2 行：x1 y1 x2 y2 （分别为起点、终点坐标）
【输出格式】：s （即最少的拐弯次数）
<b><span>Input</span> </b>
<span> 【输入输出样例】（见图1）： <br />
输入：（turn.in）
5 7
1 0 0 0 0 1 0
0 0 1 0 1 0 0
0 0 0 0 1 0 1
0 1 1 0 0 0 0
0 0 0 0 1 1 0
1 3 1 7
<b><span>Output</span> </b>
<span> 输出：(turn.out)5 </span>
Input
Output
Examples
Input
Output
Solution C++
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int map[101][101],lj[101][3],jl[101],zh[101][3]; int fx[6]={0,-1,0,1,0},fy[6]={0,0,1,0,-1}; int n,m,hd=0,tl=1,sx,sy,ex,ey,tx,ty,sum=0,ans=0; bool h=false,s=false; int pt(int x) { if(jl[x]!=0)pt(jl[x]); zh[++sum][1]=lj[x][1]; zh[sum][2]=lj[x][2]; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>map[i][j]; cin>>sx>>sy>>ex>>ey; map[sx][sy]=1;lj[1][1]=sx;lj[1][2]=sy;jl[1]=0; while(hd<=tl) { hd++; for(int i=1;i<=4;i++) { tx=lj[hd][1]+fx[i];ty=lj[hd][2]+fy[i]; if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&map[tx][ty]==0) { lj[++tl][1]=tx;lj[tl][2]=ty; map[tx][ty]=-1;jl[tl]=hd; if(tx==ex&&ty==ey) { pt(tl); if(zh[1][1]==zh[2][1])s=true; else h=true; for(int i=3;i<=sum;i++) { if(zh[i][1]==zh[i-1][1]&&!s){ans++;s=true;h=false;} if(zh[i][2]==zh[i-1][2]&&!h){ans++;h=true;s=false;} } cout<<ans<<endl; return 0; } } } } return 0; }