洛谷-奇怪的电梯 POJ-3278 （BFS）

目录

 

模拟过程：

BFS模板：

奇怪的电梯

POJ-3278

---

模拟过程：

BFS：广度优先搜索，dfs先遍历子结点再遍历兄弟结点的形式，广度优先，先遍历兄弟结点再遍历子结点。

优缺点：返回需要的最短次数，比较好的求最少操作次数或者最短路径（同权值）对于解决最短或最少问题特别有效，而且寻找深度小，但是需要消耗内存较多。

Bfs需要用到数据结构：队列。即具有先进先出的性质，可以调用C++中的queue库中，也可以自定义结构体包含需要记录的类似于坐标、位置。建立结构体数组，模拟队列先进先出。

BFS模板：

#include<queue>

数组vis标记是否被访问，step标记第几层

int bfs(){

       1.开辟队列

       queue<类型>que;

       2.情空队列

       while(!que.empty())

              que.pop();

       3.首元素进队列并标记

       que.push(first_ele); vis[first_ele];

       4.建立now,next变量，进行标记

       int now,next;

       while(!que.empty()){ 判断条件 如果都经历过了还没有跳出 就证明无解

              now = que.front();

que.pop();

for(  ){

if() next = now..

else if() next = now...

......

if(    ) continue;

vis[next] = 1;step[next]=step[now]+1;que.push(next);

if(next 满足目标位置)

       return 返回要求次数step[next]

}

       }

return 错误

} 切记不可能出现经历两次的情况，也就是说 可以先判断始点终点一样输出1 否则bfs

奇怪的电梯

#include<algorithm>

#include<cstdio>

#include<iostream>

#include<queue>



using namespace std;

int n,a,b;

int k[251];

int vis[251];

int step[251];

int bfs(){

       queue<int>que;

       while(!que.empty())

              que.pop();

       que.push(a);

       vis[a] = 1;

       int now,next;

       while(!que.empty()){

              now = que.front();

              que.pop();

              for(int i = 0;i < 2;i++){

                     if(i == 0) next = now+k[now];

                     else if(i == 1) next = now-k[now];

                     if(next < 1||next > n||vis[next] == 1) continue;

                     vis[next] = 1;

                     step[next] = step[now]+1;

                     que.push(next);

                     if(next == b)

                            return step[next];

              }

       }

       return -1;

}

int main(){    

       cin >> n >> a >> b;

       for(int i = 1;i <= n;i++)

              cin >> k[i];

       if(a == b) {cout << "0" << endl;    //不判断就输出-1 错误

       return 0;}

       int ans = bfs();

       cout << ans << endl;

}

POJ-3278

#include<algorithm>

#include<cstdio>

#include<iostream>

#include<queue>



using namespace std;



const int maxn = 1e5+10;

int vis[maxn];

int step[maxn];

int n,k;

int bfs(){

       queue<int>que;

       while(!que.empty())

              que.pop();

       que.push(n);

       vis[n] = 1;

       int now,next;

       while(!que.empty()){

              now = que.front();

              que.pop();

              for(int i = 1;i <= 3;i++){

                     if(i == 1) next = now+1;

                     else if(i == 2) next = now-1;

                     else next = now*2;

                     if(next < 1||next > maxn) continue;

                     if(!vis[next]){

                            vis[next] = 1;

                            step[next] = step[now] + 1;

                            que.push(next);

                     }

                     if(next == k)

                            return step[next];

              }

             

       }    

}

int main(){

       scanf("%d%d",&n,&k);

       int ans;

       if(n >= k)

              ans = n - k;

       else

              ans = bfs();

       printf("%d\n",ans);

       return 0;

}