主题：kuai kuai
开xindd
[专家分：0] 发布于 2007-09-02 21:08:00
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,……)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？
输入
输入文件共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)，第二行为N个用空格隔开的正整数，表示Ki。
输出
输出文件仅一行，即最少按键次数,若无法到达，则输出-1。
样例
LIFT.IN
5 1 5
3 3 1 2 5
LIFT.OUT
3
回复列表 （共3个回复）
沙发
游侠UFO [专家分：1200] 发布于 2007-09-03 00:00:00
可以用宽度优先搜索。
我的BLOG里有解法。
http://blog.sina.com.cn/s/blog_4033131f010006kx.html
板凳
Matodied [专家分：7560] 发布于 2007-09-03 21:42:00
具体搜索办法如下：
这里i只有2种操作：上（floor := floor + c[floor]），下（floor := floor - c[floor]）。
确定了操作i后，判断操作后的floor在不在1 - N范围内，如果在就进行操作。
如果被电梯困住了（即在某楼层按上、下都不行）就表示搜索失败，需要退回上一次操作。
3 楼
Matodied [专家分：7560] 发布于 2007-09-03 22:09:00
程序：
TYPE arr = ARRAY[0..255] OF INTEGER;
VAR
c, fl, s: arr; p, floor, i, n, a, b, t: INTEGER;
BEGIN
READLN(n, a, b);
FOR i:=1 TO n DO READ(c[i]);
WRITELN;
p := 0; fl[p] := a; s[p] := 0; floor := a; i := 0;
t := b - a;
REPEAT
i := i + 1;
IF i <= 2 THEN BEGIN
IF i = 1 THEN BEGIN
IF t < 0 THEN floor := fl[p] - c[fl[p]] ELSE floor := fl[p] + c[fl[p]];
END ELSE BEGIN
IF t < 0 THEN floor := fl[p] + c[fl[p]] ELSE floor := fl[p] - c[fl[p]];
END;
IF (floor >= 1) AND (floor <= n) THEN BEGIN
p := p + 1; fl[p] := floor; s[p] := i; i := 0;
END;
END ELSE BEGIN
IF p = 0 THEN BREAK;
i := s[p]; fl[p] := 0; p := p - 1;
END;
UNTIL (floor = b);
IF p = 0 THEN WRITELN(-1) ELSE WRITELN(p);
END.
我来回复
您所在位置：