首页 > 代码库 > HDU 1548 A strange lift(Dijkstra,简单BFS)

HDU 1548 A strange lift(Dijkstra,简单BFS)

2024-07-13 17:57:59   238人阅读

题目大意：

    电梯有两个选项向上或向下，每层楼有一个参数ki，代表电梯可以再该楼层的基础上向上或向下移动ki层，限制条件是向上不能超过楼层总数n，向下不能少于一。输入总层数n和当前所在层数以及目标层数，然后是n个数分别代表第i层的移动范围。输出最少移动次数，若不可达，输出-1.

解题思路：

    1.用Dijkstra算法，首先构建邻接矩阵，注意在构造时，要考虑i-k[i]<1和i+k[i]>n，i代表当前所在层。

    

 1 #include<string.h> 2 #include<stdio.h> 3 #define INF 0x3f3f3f3f 4 int k[201]; 5 int g[1001][1001]; 6 int dis[1001],vis[1001]; 7 int t,s,d,x,y; 8 int a,b,n; 9 void dijkstra(int start)10 {11     int i,j,k;12     memset(vis,0,sizeof(vis));//初始化vis数组，标记为都未访问过。13     for(i=1; i<=n; i++)14     {15         if(i==start)16             dis[i]=0;17         else18             dis[i]=INF;19     }//除起始点外，其他点的dis都赋为正无穷20     for(i=1; i<=n; i++)21     {22         int r;23         int min=INF;24         for(j=1; j<=n; j++)25             if(!vis[j]&&dis[j]<min)26             {27                 min=dis[j];28                 r=j;29             }找出当前未被访问的点中权值最小的点，对所有从该点出发的边进行松弛。30         vis[r]=1;31         for(k=1; k<=n; k++)//松弛操作32             if(dis[k]<(dis[r]+g[r][k]))33                 dis[k]=dis[k];34             else35                 dis[k]=dis[r]+g[r][k];36     }37     return;38 }39 int main()40 {41     int i;42     while(scanf("%d",&n)!=EOF&&n)43     {44         memset(g,INF,sizeof(g));45         scanf("%d%d",&a,&b);46         for(i=1; i<=n; i++)47         {48             scanf("%d",&k[i]);49         }50         for(i=1; i<=n; i++)51         {52             if(i-k[i]<1)53                 g[i][k[i]+i]=1;54             if(i+k[i]>n)55                 g[i][i-k[i]]=1;56             if(i-k[i]>=1&&i+k[i]<=n)57             {58                 g[i][k[i]+i]=1;59                 g[i][i-k[i]]=1;60             }61         }62         dijkstra(a);63         if(dis[b]==INF)64             printf("-1\n");65         else66             printf("%d\n",dis[b]);67     }68     return 0;69 }

   2.BFS算法：

         有向上走和向下走两种方法：

 1 #include <iostream> 2 #include <stdio.h> 3 #include <queue> 4 using namespace std; 5 int n, start,end; 6 int a[205]; 7 bool vis[205], flag; 8 struct node 9 {10     int x, step;//x记录当前所在层，step记录已经走了几次11 } n1, n2, m;12 int main()13 {14     int i;15     while(scanf("%d", &n)!=EOF)16     {17         if(n== 0)18             break;19         scanf("%d %d", &start,&end);20         for(i = 1; i <= n; i++)21         {22             scanf("%d", &a[i]);23             vis[i] = false;24         }25         flag = false;26         n1.x = start;27         n1.step = 0;28         queue<node> Q;29         Q.push(n1);//起始点入队列30         vis[n1.x] = true;31         while(!Q.empty())32         {33             m = Q.front();34             Q.pop();35             if(m.x == end)36             {37                 flag = true;38                 break;39             }40             n1.x = m.x - a[m.x];41             n2.x = m.x + a[m.x];42             if(n1.x>0 && n1.x<=end && !vis[n1.x])43             {44                 n1.step = m.step + 1;45                 vis[n1.x] = true;46                 Q.push(n1);47             }48             if(n2.x>0 && n2.x<=end && !vis[n2.x])49             {50                 n2.step = m.step + 1;51                 vis[n2.x] = true;52                 Q.push(n2);53             }54         }55         if(flag)56             printf("%d\n", m.step);57         else58         printf("-1\n");59     }60     return 0;61 }


联系
我们