HDOJ 1548 A strange lift

 連結：Problem - 1548 (hdu.edu.cn)

問題描述：

題目大意：

 一開始在某一層，然後根據某一層的ki上升或下降電梯，如果能到達目标層，則輸出用的次數，如果不能到達則輸出 -1.

解題思路：

運用bfs，将此問題程式設計圖的問題。

代碼實作：

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n,start,target;
int a[202],vis[202];//vis用來做标記
struct pos{
    int level;
    int step;
};

void bfs(){
    pos cur,nex;
    cur.level =start;
    cur.step = 0;
    queue <pos> qu;
    qu.push(cur);
    vis[start] = 1;
    while(!qu.empty()){
        cur =qu.front();
        qu.pop();
        if(cur.level == target){
            printf("%d\n",cur.step);
            return;
        }

        nex.level=cur.level+a[cur.level];
        nex.step=cur.step+1;
        if(nex.level<=n){
            if(vis[nex.level]==0){
                vis[nex.level] =1;
                qu.push(nex);
            }
        }
        nex.level=cur.level-a[cur.level];
        nex.step=cur.step+1;
        if(nex.level>=1){
            if(vis[nex.level]==0){
                vis[nex.level] =1;
                qu.push(nex);
            }
        }
    }
    printf("-1\n");
    return;
}

int main(){
    while(scanf("%d",&n)==1){
        if(n== 0) break;
        scanf("%d %d",&start,&target);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            vis[i]=0;
        }
        bfs();
    }
    return 0;
}