题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1548
题目大意:一栋楼有N层,有一个电梯,你在A层,要去B层。每一层有一个数字Ki,你可以选择上Ki层或是下Ki层,求最少按键次数。
解法:好吧,其实这是我练图论专题的第一题,本来可以用dj做,但我一看用bfs挺好的。。。就bfs写了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; int n,A,B,a[300],flag[300]; struct node { int x; int step; }; int main() { while (scanf("%d",&n),n) { scanf("%d %d",&A,&B); for(int i=1;i<=n;i++) scanf("%d",a+i); queue <node> q; memset(flag,0,sizeof(flag)); node temp,temp2; temp.x=A; temp.step=0; flag[A]=true; q.push(temp); while (!q.empty()) { temp=q.front(); q.pop(); if(temp.x==B) break; if(temp.x+a[temp.x]<=n&&!flag[temp.x+a[temp.x]]){ temp2.x=temp.x+a[temp.x]; temp2.step=temp.step+1; q.push(temp2); flag[temp.x+a[temp.x]]=true; } if(temp.x-a[temp.x]>0 && !flag[temp.x-a[temp.x]]){ temp2.x=temp.x-a[temp.x]; temp2.step=temp.step+1; q.push(temp2); flag[temp.x-a[temp.x]]=true; } } if(q.empty()&&temp.x!=B) printf("-1\n"); else printf("%d\n",temp.step); } return 0; }