您现在的位置是：主页 > news > 江西省美丽乡村建设公布网站/今天最新疫情情况
江西省美丽乡村建设公布网站/今天最新疫情情况
admin2025/4/30 14:19:44【news】
简介江西省美丽乡村建设公布网站,今天最新疫情情况,长春网站,做网站推广如何呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 ii 层楼 (1 \le i \le N)(1≤i≤N) 上有一个数字 K_i(0 \le K_i \le N)Ki(0≤Ki≤N) 。电梯只有四个按钮：开，关，…
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 ii 层楼 (1 \le i \le N)(1≤i≤N) 上有一个数字 K_i(0 \le K_i \le N)Ki(0≤Ki≤N) 。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： 3, 3 ,1 ,2 ,53,3,1,2,5 代表了 K_i(K_1=3,K_2=3,…)Ki(K1=3,K2=3,…) ，从 11 楼开始。在 11 楼，按“上”可以到 44 楼，按“下”是不起作用的，因为没有 -2−2楼。那么，从 AA 楼到 BB 楼至少要按几次按钮呢？
输入输出格式
输入格式：
共二行。
第一行为 3 个用空格隔开的正整数，表示 N,A,B(1≤N≤200, 1≤A,B≤N)N,A,B(1≤N≤200,1≤A,B≤N) 。
第二行为 N 个用空格隔开的非负整数，表示 K_iKi 。
输出格式：
一行，即最少按键次数,若无法到达，则输出 -1−1 。
输入输出样例
输入样例#1： 复制
5 1 5 3 3 1 2 5
输出样例#1： 复制
3
思路
已经到达的层数，若再到达一次，除了次数加一，没任何意义，所以将已经走过的层数标记。
先用bfs来做，直接将到达的层数加入优先队列，取出次数最小的，那么先到达目标层数的一定是最小的次数，直接退出
123456789 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
using namespace std;int a[210],vis[210],n;
struct node
{int x;int step;friend bool operator < (node x,node y){return x.step>y.step;}
};
void bfs(int x,int y)
{priority_queue<node> que;node e1,e2;e1.x=x;e1.step=0;vis[x]=0; // 标记que.push(e1);int res=-1;while(que.size()){e1=que.top();que.pop();if(e1.x==y){ // 次数最小，直接记录退出res=e1.step;break;}if(e1.x+a[e1.x]<=n&&vis[e1.x+a[e1.x]]){e2.step=e1.step+1;e2.x=e1.x+a[e1.x];vis[e2.x]=0;que.push(e2);}if(e1.x-a[e1.x]>=1&&vis[e1.x-a[e1.x]]){e2.step=e1.step+1;e2.x=e1.x-a[e1.x];vis[e2.x]=0;que.push(e2);}}cout << res << endl;
}
int main()
{int x,y,i,j; cin >> n >> x >> y;for(i=1;i<=n;i++){cin >> a[i];vis[i]=1;}bfs(x,y);
} |
相比之下，dfs代码简洁，但是并不好写。也是记录当前最小的次数，凡是大于该次数的直接剪枝。
123456789 10 11 12 | void dfs(int x,int k)
{if(x==y){res=min(res,k);}else if(k<=res){ // 剪枝vis[x]=false; // 标记来过if(x+a[x]<=n&&vis[x+a[x]])dfs(x+a[x],k+1);if(x-a[x]>=1&&vis[x-a[x]])dfs(x-a[x],k+1);vis[x]=true; // 回溯}
} |
虽说dfs更短，但个人更倾向于bfs。你觉得呢？
