#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,step;
}c,d;
int n,m,vis[1005][1005]={},a[1005][1005];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
queue<node>que;
void bfs()
{
vis[c.x][c.y]=1;
node head=que.front();
while(que.size())
{
for(int i=0;i<4;i++)
{
int nx=head.x+dx[i],ny=que.front().y+dy[i];
while(nx>=1 and nx<=n and ny>=1 and ny<=m and a[nx][ny]==0)
{
if(vis[nx][ny]==-1)
{
if(nx==d.x and ny==d.y)
{
cout<<head.step;
return;
}
vis[nx][ny]=1;
que.push({nx,ny,head.step+1});
nx+=dx[i];
ny+=dy[i];
}
}
}
que.pop();
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
cin>>c.x>>c.y>>d.x>>d.y;
que.push(node{c.x,c.y,0});
memset(vis,-1,sizeof vis);
bfs();
}
2. 最小转弯路径
XJOI - 题目ID：8121必做题50分
时间限制: 100ms
空间限制: 131072kB
题目描述
时间限制：0. 1s 空间限制：128 M
题目描述：
给出一个地图，求起点到终点的最少转弯次数，如果没有可行路径，则输出 -1。
输入格式：
第一行输入 n 和 m，表示行和列数。
接下来 n*m 的矩阵，0 表示可以走，1 表示不能走。
接下来的一行有 4 个数字，表示起点和终点的位置。
输出格式：
一个整数，表示最少的转弯次数。
样例输入：
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
样例输出：
5