最小转弯路径
XJOI - 题目ID：8121必做题50分
最新提交：0 分
历史最高：0 分
时间限制: 100ms
空间限制: 131072kB
题目描述
时间限制：0. 1s 空间限制：128 M
题目描述：
给出一个地图，求起点到终点的最少转弯次数，如果没有可行路径，则输出 -1。
输入格式：
第一行输入 n 和 m，表示行和列数。(2≤�,�≤100)(2≤n,m≤100)
接下来 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
我的代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},vis[1005][1005]={};
int s[1005][1005];
struct node{
int x,y,l1,l2;
}st,sd;
queue<node> que;
int bfs(){
que.push(node{st.x,st.y,0,0});
for(int i = 1; i<=n; i++){
for(int j = 1; j<=m; j++){
vis[i][j] = INT_MAX;
}
}
vis[st.x][st.y] = 0;
while(que.size()){
node now = que.front();
que.pop();
for(int i = 0; i<4; i++){
int xx=now.x+dx[i],yy=now.y+dy[i];
if(xx>0 && xx<=n && yy<=m && yy>0 && s[xx][yy] != 1 && vis[now.x][now.y]<=vis[xx][yy]){
// cout<<xx<<" "<<yy<<endl;
int t = INT_MAX;
if(dx[i] != now.l1 || dy[i] != now.l2){
t = vis[now.x][now.y]+1;
// cout<<1<<endl;
}
if(t<vis[xx][yy]){
vis[xx][yy] = t;
}else{
vis[xx][yy] = vis[now.x][now.y];
}
que.push(node{xx,yy,dx[i],dy[i]});
}
}
}
return vis[sd.x][sd.y];
}
int main(){
cin>>n>>m;
for(int i = 1; i<=n; i++){
for(int j = 1; j<=m; j++){
cin>>s[i][j];
}
}
cin>>st.x>>st.y>>sd.x>>sd.y;
int ans = bfs();
cout<<ans-1;
return 0;
}