题目描述
最短路直接bfs就欧克了,俺只会暴力hhh
算法1
(宽度优先搜索)
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=110;
int dis[N];
int startx,endy,portalx,portaly;
int bfs(){
memset(dis,-1,sizeof dis);//初始化顺便做标记
queue<int> q;
q.push(startx);//将起点加入队列
dis[startx]=0;
while(q.size()){
int t=q.front();q.pop();
if(t==endy) break;
int x1=t+1;
if(x1>=0&&x1<=100&&dis[x1]==-1){//前进一步
q.push(x1);
dis[x1]=dis[t]+1;
}
int x2=t-1;
if(x2>=0&&x2<=100&&dis[x2]==-1){
q.push(x2); //后退一步
dis[x2]=dis[t]+1;
}
if(t==portalx&&dis[portaly]==-1){
q.push(portaly); //传送门距离不加
dis[portaly]=dis[t];
}
if(t==portaly&&dis[portalx]==-1){
q.push(portalx); //传送门距离不加
dis[portalx]=dis[t];
}
}
return dis[endy];//返回起点到终点的最小距离
}
int main(){
cin >> startx >> endy >> portalx >> portaly;
int res=bfs();
cout << res;
}