首页 > 搜索 > BFS搜索 > HDU 1548 A strange lift-BFS-[解题报告] C++
2013
12-12

HDU 1548 A strange lift-BFS-[解题报告] C++

A strange lift

问题描述 :

There is a strange lift.The lift can stop can at every floor as you want, and there is a number Ki(0 <= Ki <= N) on every floor.The lift have just two buttons: up and down.When you at floor i,if you press the button "UP" , you will go up Ki floor,i.e,you will go to the i+Ki th floor,as the same, if you press the button "DOWN" , you will go down Ki floor,i.e,you will go to the i-Ki th floor. Of course, the lift can’t go up high than N,and can’t go down lower than 1. For example, there is a buliding with 5 floors, and k1 = 3, k2 = 3,k3 = 1,k4 = 2, k5 = 5.Begining from the 1 st floor,you can press the button "UP", and you’ll go up to the 4 th floor,and if you press the button "DOWN", the lift can’t do it, because it can’t go down to the -2 th floor,as you know ,the -2 th floor isn’t exist.
Here comes the problem: when you are on floor A,and you want to go to floor B,how many times at least he has to press the button "UP" or "DOWN"?

输入:

The input consists of several test cases.,Each test case contains two lines.
The first line contains three integers N ,A,B( 1 <= N,A,B <= 200) which describe above,The second line consist N integers k1,k2,….kn.
A single 0 indicate the end of the input.

输出:

For each case of the input output a interger, the least times you have to press the button when you on floor A,and you want to go to floor B.If you can’t reach floor B,printf "-1".

样例输入:

5 1 5
3 3 1 2 5
0

样例输出:

3

题目:http://acm.hdu.edu.cn/showproblem.php?pid=1548

 

玩了两天,差点写不出了。。。。。。。

这题是由某个状态遍历其他状态的BFS

对于某一状态下有—->所在层:now_floor,从开始到该层按了几次按钮:step。。。。。

 

#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

const int INF = 1 << 30;

int a[222];
bool vis[222];
int n;

struct point
{
    int now_floor, step;
};


int Bfs(int star, int end)
{
    memset(vis, 0, sizeof(vis));
    point q1, q2;
    queue <point> q;
    q1.now_floor = star - 1;
    q1.step = 0;
    q.push(q1);
    vis[q1.now_floor] = 1;

    while (!q.empty())
    {
        q2 = q.front();
        q.pop();

        if (q2.now_floor == end - 1)
        {
            return q2.step;
        }

        q1.now_floor = q2.now_floor + a[q2.now_floor];
        q1.step = q2.step + 1;
        if (q1.now_floor < n && q1.now_floor >= 0 && !vis[q1.now_floor])
        {

            q.push(q1);
            vis[q1.now_floor] = 1;
        }

        q1.now_floor = q2.now_floor - a[q2.now_floor];

        if (q1.now_floor >= 0 && q1.now_floor < n && !vis[q1.now_floor])
        {
            q.push(q1);
            vis[q1.now_floor] = 1;
        }
    }
    return -1;

}

int main()
{

    int i, j;
    int ans;
    int star, end;

    while (~scanf("%d", &n), n)
    {
        scanf("%d%d", &star, &end);
        for (i = 0; i < n; i++)
        {
            scanf("%d", a + i);
        }

        
        printf("%d\n", Bfs(star, end));

    }

    return 0;
}

解题报告转自:http://www.cnblogs.com/qiufeihai/archive/2012/04/09/2439385.html


,
  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  4. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  5. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  6. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  7. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。