首页 > 代码库 > HDU 1548 (最基础的BFS了) A strange lift

HDU 1548 (最基础的BFS了) A strange lift

2024-07-17 22:32:10   220人阅读

这是一维的BFS，而且没有什么变形，应该是最基础的BFS了吧

题意：

有这样一个奇葩的电梯，你在第i层的时候你只能选择上或者下Ki层，也就是你只能从第i层到达i+Ki或者i-Ki层。当然电梯最低只能在1层最高只能在n层。

给出起点和终点问最少需要多少次才能到达终点，如果不能到达输出-1

 

没有什么好解释的了，如此单纯的一道题，只要不是太粗心就能A过去

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 200 + 10; 8 struct Point 9 {10     int h;11     int times;12 }qu[maxn];13 int n, from, to, go[maxn], vis[maxn];14 int head, tail;15 int dir[2] = {1, -1};16 17 void BFS(void)18 {19     head = 0, tail = 1;20     qu[0].h = from, qu[0].times = 0;21     while(head < tail)22     {23         if(qu[head].h == to)24         {25             printf("%d\n", qu[head].times);26             return;27         }28         for(int i = 0; i < 2; ++i)29         {30             int hh = qu[head].h + go[qu[head].h]*dir[i];31             if(hh>0 && hh<=n && (!vis[hh]))32             {33                 vis[hh] = 1;34                 qu[tail].h = hh;35                 qu[tail++].times = qu[head].times + 1;36             }37         }38         ++head;39     }40     printf("-1\n");41 }42 43 int main(void)44 {45     #ifdef LOCAL46         freopen("1548in.txt", "r", stdin);47     #endif48 49     while(scanf("%d", &n) == 1 && n)50     {51         scanf("%d%d", &from, &to);52         for(int i = 1; i <= n; ++i)53             scanf("%d", &go[i]);54         memset(vis, 0, sizeof(vis));55         BFS();56     }57     return 0;58 }
代码君

 


联系
我们