HDU- 1548 A strange lift (DFS)

矫情吗；* 2022-05-19 00:24 130阅读 0赞

## **                                                A strange lift** ##

### **Problem Description** ###

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"?

### **Input** ###

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.

### **Output** ###

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".

### **Sample Input** ###

5 1 5

3 3 1 2 5

### **Sample Output** ###

**题意描述：**  
一部只能上或者下所在层上的数字的电梯，求从A层到B层的最短按键次数。

**解题思路：**  
利用深搜，book\[\]数组记录的是到所在层的最短步数，a\[\]数组记录所在层数字；当楼层不合理返回；当到达B层且步数更小时更新最小步数并返回；当步数大于等于所在层记录的最短步数时返回。

#include<stdio.h>
    int s[201],book[201],step,num,i,a,n,b;//s[]数组记录每个楼层上的数字，book[]数组记录到楼层的步数 
    void dfs(int i,int step);
    int main()
    {
    	while(scanf("%d",&n))
    	{
    		if(n==0)
    			break;
    		scanf("%d%d",&a,&b);
    		for(i=1;i<=n;i++)
    		{
    			scanf("%d",&s[i]);
    			book[i]=99999999; 
    		}
    		num=99999999;
    		dfs(a,0);
    		if(num==99999999)
    			printf("-1\n");
    		else
    			printf("%d\n",num);
    	}
    	return 0;
    }
    void dfs(int i,int step)
    {
    	if(i<1||i>n)
    		return;
    	if(i==b&&step<num)
    	{
    		num=step;
    		return;
    	}
    	if(step>=book[i])//若此时到i楼的步数小于等于记录的到i楼的步数，返回 
    		return;
    	book[i]=step;
    	dfs(i+s[i],step+1);
    	dfs(i-s[i],step+1);
    	return;
    }