1.原题
2.分析
这道题在网上找一般都是用BFS解答，用BFS可以很方便的求最少步数。但老师要求用DFS解答来联系回溯剪枝。
这道题目和 加1乘2平方 很相似，只有两个状态：上和下。N最大为200，如果不剪枝的话，有2^200次递归，很容易就爆栈了。
3.AC代码
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <stdio.h>
using namespace std
;
#define MAX 500
int T
, A
, B
;
int K
[201];
int a
[201];
void dfs(int now
, int stp
)
{
if (a
[now
] > stp
)
{
a
[now
] = stp
;
int newf
= now
+ K
[now
];
if (newf
<= T
)
dfs(newf
, stp
+ 1);
newf
= now
- K
[now
];
if (newf
>= 1)
dfs(newf
, stp
+ 1);
}
}
int main()
{
cin
>> T
>> A
>> B
;
int i
;
for (i
= 0; i
<= 200; i
++)
{
a
[i
] = MAX
;
}
for (i
= 1; i
<= T
; i
++)
{
cin
>> K
[i
];
}
dfs(A
, 0);
if (a
[B
]!=500)
{
cout
<< a
[B
];
}
else
{
cout
<< -1;
}
}
