bfs 简单模板题求解答

#include<stdio.h>
#include <math.h> 
#include <queue>
#include <string.h>
using namespace std;
int to[2]={1,-1};
int step,n,ex,t1,t2;
int k[202];
int map[202];
struct node
{
    int x,step;
};

int check(int x){
    if(x<0||x>n)
        return 1;
    return 0;
}
int bfs(){
    queue<node> Q;
    node p,next,q;
    p.x=t1;
    p.step=0;
    ex=t2;
    Q.push(p);
    while (!Q.empty()){
        q=Q.front();
        Q.pop();
        if(q.x==ex)
            return q.step;
        for (int j=1;j<=n;j++)
            for(int i=0;i<=1;i++){
                next.x=q.x+to[i]*k[j];
                if(next.x==ex)
                    return q.step+1;
                if(check(next.x))
                    continue;
                next.step=q.step+1;
                Q.push(next);
                }
            } 
        return 0; 
}  
int main(){
    while(scanf("%d",&n)!=EOF&&n){
        scanf("%d%d",&t1,&t2);
        for (int i=1;i<=n;i++)
            scanf("%d",&k[i]);

        printf("%d\n",bfs()); 
    }
    return 0;
}

题没看懂，4-2为什么等于-2

一种正解：

#include
using namespace std;
int main()
{
int n;
while(scanf("%d",&n)!=EOF && n)
{
int d[201][201]={0},dis[201]={0},f[201]={0};
int a,b;
cin>>a>>b;
for (int i=1;i<=n;++i)
{
for (int j=1;j<=n;++j)
d[i][j]=1000000;
d[i][i]=0;
}
int k;
for (int i=1;i<=n;++i)
{
cin>>k;
if (i+k<=n) d[i][i+k]=1;
if (i-k>=1) d[i][i-k]=1;
}
for (int i=1;i<=n;++i)
dis[i]=d[a][i];
int minn,t;
for (int i=1;i<=n;++i)
{
minn=1000000;
for (int j=1;j<=n;++j)
if (f[j]==0&&dis[j]<minn)
{
minn=dis[j];
t=j;
}
f[t]=1;
for (int j=1;j<=n;++j)
dis[j]=min(dis[j],dis[t]+d[t][j]);
}
if (dis[b]!=1000000)
cout<<dis[b];
else
cout<<-1;
}
return 0;
}