首页 > 代码库 > hdu1548 A strange lift(bfs 或Dijkstra最短路径)

hdu1548 A strange lift(bfs 或Dijkstra最短路径)

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define M 205 6 #define INF 0x3f3f3f3f 7 using namespace std; 8  9 int map[M][M];10 int d[M], vis[M];11 int n;12 int b, e;13 14 void Dijkstra(){15    memset(d, 0x3f, sizeof(d));16    memset(vis, 0, sizeof(vis));17    d[b]=0;18    vis[b]=1;19    int root=b;20    for(int j=1; j<n; ++j){21        int minLen=INF, p;    22        for(int i=1; i<=n; ++i){23           if(!vis[i] && d[i] > d[root] + map[root][i])24               d[i] = d[root] + map[root][i];        25           if(!vis[i] && minLen>d[i]){26              p=i;27              minLen=d[i];           28           }29        }30        if(minLen==INF)31           return;32        root=p;33        vis[root]=1;34    }     35 }36 37 int main(){38    while(cin>>n && n){39        cin>>b>>e;40        memset(map, 0x3f, sizeof(map));41        for(int i=1; i<=n; ++i){42           int x, xx;43           cin>>x;44           map[i][i]=0;// i+(-)x 表示 从第i层可以到达第 i+(-)x层 45           xx=i-x;46           if(xx>=1) map[i][xx]=1;47           xx=i+x;48           if(xx<=n)  map[i][xx]=1;      49        }             50        Dijkstra();51        if(d[e]==INF)52           cout<<"-1"<<endl;53        else54           cout<<d[e]<<endl;55    }56    return 0;57 } 

 

 1 /* 2 思路:当前电梯位置的两个方向进行搜索!  3       注意:搜索时的界限, 用x表示将要到达的电梯的位置  4             1. 首先是x>=1  5             2. x<=n 6             3. vis[x]!=0 表明bfs时候没有经过这个楼层  7 */ 8 #include<iostream> 9 #include<cstring>10 #include<cstdio>11 #include<queue> 12 using namespace std;13 struct node{14    int x;15    int step;       16    node(){}17    node(int x, int step){18       this->x=x;19       this->step=step;         20    }21 };22 queue<node>q;23 int n, b, e;24 int f[205];25 int vis[205];26 27 bool bfs(){28     while(!q.empty())  q.pop();29     memset(vis, 0, sizeof(vis)); 30     q.push(node(b,0));31     vis[b]=1;32     while(!q.empty()){33         node cur=q.front();34         q.pop();35         if(cur.x==e){36             cout<<cur.step<<endl;37             return true;             38         }               39         int xx;40         xx=cur.x+f[cur.x];41         if(xx==e){42            cout<<cur.step+1<<endl;43            return true;44         }45         if(xx<=n && !vis[xx]){46            q.push(node(xx, cur.step+1));47            vis[xx]=1;48         }49         xx=cur.x-f[cur.x];50         if(xx==e){51            cout<<cur.step+1<<endl;52            return true;53         }54         if(xx>=1 && !vis[xx]){55            q.push(node(xx, cur.step+1));56            vis[xx]=1;57         }58     }59     return false;60 }61       62 int main(){63     while(cin>>n && n){64        cin>>b>>e;65        for(int i=1; i<=n; ++i)66           cin>>f[i];67        if(!bfs())68           cout<<"-1"<<endl;            69     }70     return 0;    71 }