我用兩種方法做，DFS沒有AC，不知道錯在哪裡，貼出來有大神撸過不吝賜教，第二種經典方法BFS過了，76MS 360k，思路都很簡單，也是一道很規范的廣度優先搜索。
代碼：
BFS：
[cpp]
#include <iostream>
#include <queue>
using namespace std;
int n,a,b;
bool visit[210];
int ki[210];
struct node{
int x,step;
}p,q;
queue<node> Q;
int bfs(){
while(!Q.empty())Q.pop();
p.x=a;
p.step=0;
Q.push(p);
visit[p.x]=1;
if(p.x==b)return 0;
while(!Q.empty())
{
p=Q.front();
Q.pop();
if(p.x==b)return p.step;
for(int i=0;i<2;i++)
{
if(i==0){
q.x=p.x+ki[p.x];
if(q.x>n)continue;
if(visit[q.x])continue;
q.step=p.step+1;
visit[q.x]=1;
Q.push(q);
}
if(i==1){
q.x=p.x-ki[p.x];
if(q.x<1)continue;
if(visit[q.x])continue;
q.step=p.step+1;
visit[q.x]=1;
Q.push(q);
}
}
}
return -1;
}
int main()
{
while(cin>>n)
{
if(n==0)break;
cin>>a>>b;
for(int i=1;i<=n;i++)
cin>>ki[i];
memset(visit,0,sizeof(visit));
cout<<bfs()<<endl;
}
return 0;
}
#include <iostream>
#include <queue>
using namespace std;
int n,a,b;
bool visit[210];
int ki[210];
struct node{
int x,step;
}p,q;
queue<node> Q;
int bfs(){
while(!Q.empty())Q.pop();
p.x=a;
p.step=0;
Q.push(p);
visit[p.x]=1;
if(p.x==b)return 0;
while(!Q.empty())
{
p=Q.front();
Q.pop();
if(p.x==b)return p.step;
for(int i=0;i<2;i++)
{
if(i==0){
q.x=p.x+ki[p.x];
if(q.x>n)continue;
if(visit[q.x])continue;
q.step=p.step+1;
visit[q.x]=1;
Q.push(q);
}
if(i==1){
q.x=p.x-ki[p.x];
if(q.x<1)continue;
if(visit[q.x])continue;
q.step=p.step+1;
visit[q.x]=1;
Q.push(q);
}
}
}
return -1;
}
int main()
{
while(cin>>n)
{
if(n==0)break;
cin>>a>>b;
for(int i=1;i<=n;i++)
cin>>ki[i];
memset(visit,0,sizeof(visit));
cout<<bfs()<<endl;
}
return 0;
}
DFS:
[cpp]
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <fstream>
#include <queue>
using namespace std;
int n,a,b,cnt,flag;
int cmin;
bool visit[210];
int ki[210];
void dfs(int x){
if(x==b){
flag=1;
if(cnt<cmin)cmin=cnt;
return ;
}
if(flag)return ;
if(x+ki[x]<=n){
if(!visit[x+ki[x]]){
cnt++;
visit[x+ki[x]]=1;
dfs(x+ki[x]);
visit[x+ki[x]]=0;
cnt--;
}
}
if(x-ki[x]>=1){
if(!visit[x-ki[x]]){
cnt++;
visit[x-ki[x]]=1;
dfs(x-ki[x]);
visit[x-ki[x]]=0;
cnt--;
}
}
}
int main()
{
//ifstream fin;
//fin.open("data1.txt");
while(cin>>n)
{
if(n==0)break;
cin>>a>>b;
for(int i=1;i<=n;i++)
cin>>ki[i];
cnt=0;
cmin=999999;
flag=0;
memset(visit,0,sizeof(visit));
visit[a]=1;
dfs(a);
if(flag)
cout<<cmin<<endl;
else cout<<-1<<endl;
}
return 0;
}
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <fstream>
#include <queue>
using namespace std;
int n,a,b,cnt,flag;
int cmin;
bool visit[210];
int ki[210];
void dfs(int x){
if(x==b){
flag=1;
if(cnt<cmin)cmin=cnt;
return ;
}
if(flag)return ;
if(x+ki[x]<=n){
if(!visit[x+ki[x]]){
cnt++;
visit[x+ki[x]]=1;
dfs(x+ki[x]);
visit[x+ki[x]]=0;
cnt--;
}
}
if(x-ki[x]>=1){
if(!visit[x-ki[x]]){
cnt++;
visit[x-ki[x]]=1;
dfs(x-ki[x]);
visit[x-ki[x]]=0;
cnt--;
}
}
}
int main()
{
//ifstream fin;
//fin.open("data1.txt");
while(cin>>n)
{
if(n==0)break;
cin>>a>>b;
for(int i=1;i<=n;i++)
cin>>ki[i];
cnt=0;
cmin=999999;
flag=0;
memset(visit,0,sizeof(visit));
visit[a]=1;
dfs(a);
if(flag)
cout<<cmin<<endl;
else cout<<-1<<endl;
}
return 0;
}
