A strange lift(HDU-1548)
本题的题意大致为,一栋楼有N层,一个人想从A层到B层去,其中电梯在不同的层数上能够上下移动的层数不同,问最短需要操作几次电梯?
分析下题目给的测试样例:
5 1 5
3 3 1 2 5
意味着一共有五层楼,这个人希望从第一楼到第五楼去,其中电梯在一楼可以选择向上或者向下三层,二楼可以向上或者向下三层,三楼可以向上或者向下一层,四楼可以向上或者向下两层,五楼可以向上或者向下五层。
手推一遍可以发现:
- 一楼可以到达4层
- 二楼可以到达5层
- 三楼可以到达2层,4层
- 四楼可以到达2层
- 五楼哪也去不了
不难发现最短的路径即为 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;
}