HDU/HDOJ 1548 A strange lift BFS，DFS (一)

我用两种方法做，DFS没有AC，不知道错在哪里，贴出来有大神撸过不吝赐教，第二种经典方法BFS过了，76MS 360k，思路都很简单，也是一道很规范的广度优先搜索。

代码：

BFS：

[cpp]
#include
#include
using namespace std;
int n,a,b;
bool visit[210];
int ki[210];
struct node{
int x,step;
}p,q;
queue 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< }
return 0;
}

#include
#include
using namespace std;
int n,a,b;
bool visit[210];
int ki[210];
struct node{
int x,step;
}p,q;
queue 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< }
return 0;
}
DFS:

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 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< else cout<<-1< }

return 0;

}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n,a,b,cnt,flag;
int cmin;
bool visit[210];
int ki[210];
void dfs(int x){
if(x==b){