洛谷 P1135 奇怪的电梯 C语言 bfs

题目：

https://www.luogu.com.cn/problem/P1135#submit

我们会发现只走过一次楼层远比走过多次更快到达目标楼层，我画了个图，所以需要用状态数组标记已经走过的楼层。

之后就是简单的bfs格式，注意，上下楼要有两个分支，所以我使用两个if两个结构体类型的对象存探索出来的楼层，或者用一个数组exfloor储存上下楼层的值再进行判断是否越界。

代码如下：

#include <iostream>
#include <climits>
#include<algorithm>
#include <cstring>
#include<queue>
using namespace std;
int N, A, B;
bool found;
int moves[10000];
bool stl[10000];
int exfloor[3];//临时储存探索楼层 
bool check(int n)//n为传过来的楼层，进行界限判断
{
if(n <= N && n >= 1)
return true;
else
return false;
 } 
struct Node{
int floor;//当前楼层 
int cnt; //使用按钮次数 
};
int main() 
{
    cin >> N >> A >> B; 
    for (int i = 1; i <= N; i++) 
        cin >> moves[i];
        
    queue <Node> q;//创建队列 
Node start;
start.floor = A;//初始楼层 
start.cnt = 0;//初始次数 
q.push(start);//压入队首 
stl[A] = true;//初始楼层标记已访问
 
while(!q.empty())
{
int x = q.front().floor;//取出队首的当前楼层和使用按钮次数 
int ans = q.front().cnt; 

if(x == B)
{
found = true; 
break;
 } 

exfloor[1] = x + moves[x];//上楼
exfloor[2] = x - moves[x];//下楼

for(int i = 1 ; i <= 2 ;i++)
{
if(check(exfloor[i]) && stl[exfloor[i]] == false)
{
stl[exfloor[i]] = true;//新楼层标记已访问 
Node newfloor;//临时新楼层 
newfloor.floor = exfloor[i];//探索楼层 
newfloor.cnt = ans + 1;//按钮次数+1 
q.push(newfloor);//压入队列 
}
 } 
/*if( x + moves[x] <= N && stl[x + moves[x]] == false)
{
Node pexfloor;//探索的新楼层 
pexfloor.floor = x + moves[x];//更新楼层 
pexfloor.cnt = ans + 1; //按钮次数加1 
q.push(pexfloor); //压入队列 
stl[pexfloor.floor] = true;//探索楼层已访问 
}

if(x - moves[x] >= 1 && stl[x - moves[x]] == false)
{
Node rexfloor;//探索的新楼层 
rexfloor.floor = x - moves[x];//更新楼层 
rexfloor.cnt = ans + 1; //按钮次数加1 
q.push(rexfloor); //压入队列 
stl[rexfloor.floor] = true;//探索楼层已访问 
}*/
q.pop();//出队首 
}
if(found)
cout << q.front().cnt;
else
cout << -1;
    return 0;
}

原文地址：https://blog.csdn.net/zqystca/article/details/144092626

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！