HDU-1548 A strange lift

A strange lift(HDU-1548)

原题传送门

本题的题意大致为,一栋楼有N层,一个人想从A层到B层去,其中电梯在不同的层数上能够上下移动的层数不同,问最短需要操作几次电梯?

分析下题目给的测试样例:

5 1 5
3 3 1 2 5

意味着一共有五层楼,这个人希望从第一楼到第五楼去,其中电梯在一楼可以选择向上或者向下三层,二楼可以向上或者向下三层,三楼可以向上或者向下一层,四楼可以向上或者向下两层,五楼可以向上或者向下五层。

手推一遍可以发现:

  1. 一楼可以到达4层
  2. 二楼可以到达5层
  3. 三楼可以到达2层,4层
  4. 四楼可以到达2层
  5. 五楼哪也去不了

不难发现最短的路径即为 1 -->4 -->2 -->5,即3次辗转即可。

解题思路一:最短路

经过上述的分析不难发现,该问题可以抽象为一个图论的问题,且是有向图,每一次移动的代价都是1,因此我们只需要从起点出发,更新到所有点的距离,迭代完后即可求得到目标点的距离。

如下是spfa算法解题的代码:

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int sp;
int n,be,en;
int h[N],ne[N],e[N],idx;
int dist[N];
bool v[N];

void add(int a,int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

//因为可能有多条输入,所以每次都得重新Init下所有参数
void Init()
{
    memset(h, -1, sizeof h);
    memset(ne, 0, sizeof ne);
    memset(e, 0, sizeof e);
    memset(v, false, sizeof v);
    idx = 0;
}
int spfa()
{
    queue<int>  q;
    memset(dist, 0x3f, sizeof dist);
    dist[be] = 0;
    q.push(be);
    v[be] = true;
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        v[t] = false;
        
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + 1)
            {
                dist[j] = dist[t] + 1;
                if(!v[j])
                {
                    q.push(j);
                    v[j] = true;
                }
            }
        }
    }
    return dist[en] == 0x3f3f3f3f?-1:dist[en];
} 

int main()
{
    while(1)
    {
        Init();
        scanf("%d%d%d",&n,&be,&en);
        if(n == 0) break;
        for(int i = 1; i <= n; i ++)
        {
            int to;
            scanf("%d",&to);
            if(i - to >= 1)    add(i,i - to);
            if(i + to <= n)    add(i,i + to);
        }
        
        int t = spfa();
        
        printf("%d\n",t);
    }
    return 0;
}

解题思路二:bfs

当点与点之间的距离为1的时候,这时候的bfs也可以求得两点之间的最短路。根据该特性也可以破该题目。

但是要注意的是,一定要自己特判起点和终点是否相同,因为bfs不会倒回来搜起点本身!!

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int sp;
int n,be,en;
int h[N],ne[N],e[N],idx;
int dist[N];
bool v[N];

void add(int a,int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void Init()
{
    memset(h, -1, sizeof h);
    memset(ne, 0, sizeof ne);
    memset(e, 0, sizeof e);
    memset(v, false, sizeof v);
    idx = 0;
}

int bfs()
{
    queue<int> q;
    memset(dist, 0, sizeof dist);
    q.push(be);
    v[be] = true;
    
    if(be == en)    return 0;
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            
            if(j == en) return dist[t] + 1;
            
            if(!v[j])
            {
                dist[j] = dist[t] + 1;
                q.push(j);
                v[j] = true;
            }
        }
    }
    return -1;
    
}

int main()
{
    while(1)
    {
        Init();
        scanf("%d%d%d",&n,&be,&en);
        if(n == 0) break;
        for(int i = 1; i <= n; i ++)
        {
            int to;
            scanf("%d",&to);
            if(i - to >= 1)    add(i,i - to);
            if(i + to <= n)    add(i,i + to);
        }
     
        int t = bfs();
        
        printf("%d\n",t);
    }
    return 0;
}
上一篇:P2258 [NOIP2014 普及组] 子矩阵


下一篇:P2294 [HNOI2005]狡猾的商人