广度优先搜索
广度优先搜索算法(Breadth-First Search,BFS)又称宽度优先搜索,是一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验法则算法。
奇怪的电梯
题目描述
呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第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楼至少要按几次按钮呢?
输入格式
共二行。
第一行为33个用空格隔开的正整数,表示N,A,B(1≤N≤200, 1≤A,B≤N)N,A,B(1≤N≤200,1≤A,B≤N)。
第二行为NN个用空格隔开的非负整数,表示K_iKi。
输出格式
一行,即最少按键次数,若无法到达,则输出-1−1。
输入输出样例
输入 #15 1 5 3 3 1 2 5输出 #13
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int a[100000]; bool b[10000]; int dl[100000][5]; int main() { int h,x,s,x1,x2,y1,y2; cin>>h>>x>>s; for(int i=1;i<=h;i++) cin>>a[i]; int head=0,tail=1; dl[1][0]=0; dl[1][1]=x; do { head++; if(dl[head][1]==s) { cout<<dl[head][0]; return 0; } x1=a[dl[head][1]]+dl[head][1]; x2=dl[head][1]-a[dl[head][1]]; if(x1>0&&(!b[x1])) { b[x1]=1; dl[++tail][1]=x1; dl[tail][0]=dl[head][0]+1; } if(x2>0&&(!b[x2])) { b[x2]=1; dl[++tail][1]=x2; dl[tail][0]=dl[head][0]+1; } }while(head<tail); cout<<"-1"; }