HDU 1548 A strange lift広捜と最短路

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1548
 
2つのボタンUPとDOWNがあって、あなたにいくつかの数iをあげて層数を表して、しかも各層の対応するKi、UPボタンを押すと、第i層から第i+Ki層に上がります;DOWNを押すとi層目からi-Ki層目に下がります.届く層数を1~Nと定め、常識によっても分かる.今の要求はあなたにN、A、Bと一連の数K 1からKnをあげて、あなたにAからBまで聞いて、少なくともいくつかのボタンを押します.
 
解法はいくつかあります.
解法一:最短ルートの解:
 
コード:
 

#include<iostream>
using namespace std;
#define INF 100000000
int map[205][205];
int dist[205],S[205];
int N,A,B;
int  Dijkstra(int u,int v)
{
    memset(S,0,sizeof(S));
    int i,j,k;
    for(i=1;i<=N;i++)
    {
        dist[i]=map[u][i];
    }
    S[u]=1;
    dist[u]=0;
    for(i=1;i<N;i++)
    {
        int min=INF,t;
        for(j=1;j<=N;j++)
        {
            if(!S[j]&&dist[j]<min)
            {
                t=j;
                min=dist[j];
            }
        }
        if(min==INF)//      A B     
            return -1;
        if(t==v)//   B
            return min;
        S[t]=1;
        for(k=1;k<=N;k++)
        {
            if(!S[k]&&dist[t]+map[t][k]<dist[k])
                dist[k]=dist[t]+map[t][k];
        }
    }
    return -1;
}
int main()
{
    int i,j,c;
    while(cin>>N,N)
    {
        cin>>A>>B;
        
        for(i=1;i<=N;i++)
        {
            for(j=1;j<=N;j++)
                map[i][j]=i==j?0:INF;
        }
        for(i=1;i<=N;i++)
        {
            cin>>c;
            if(i+c<=N)
                map[i][i+c]=1;
            if(i-c>=1)
                map[i][i-c]=1;
        }
        if(A==B)//          i i    
        {
            cout<<"0"<<endl;
        }
        else
            cout<<Dijkstra(A,B)<<endl;
    }
    return 0;
}

第二の解法:広捜
コード:
 

#include<iostream>
using namespace std;
#include<queue>
int n;
struct node{
    int c;
    int num;
}m,n1,n2,t;
queue<node> Q;
int main()
{
    int a,b,c[205],s;
    bool map[205],flag;
    int i;
    while(~scanf("%d",&n),n)
    {
        scanf("%d%d",&a,&b);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&c[i]);
            map[i]=false;
        }
        if(a==b)
        {
            printf("0
");
            continue;
        }
        m.c=a;
        m.num=0;
        Q.push(m);
        map[m.c]=true;
        flag=false;
        while(!Q.empty())
        {
            t=Q.front();
            Q.pop();
            if(t.c==b)
            {
                flag=true;
                s=t.num;
                break;
            }
            n1.c=t.c+c[t.c];
            if(n1.c>=1&&n1.c<=n&&!map[n1.c])
            {
                n1.num=t.num+1;
                Q.push(n1);
                map[n1.c]=true;
            }
            n2.c=t.c-c[t.c];
            if(n2.c>=1&&n2.c<=n&&!map[n2.c])
            {
                n2.num=t.num+1;
                Q.push(n2);
                map[n2.c]=true;
            }
        }
        if(flag==true)
            printf("%d
",s);
        else
            printf("-1
");
        while(!Q.empty())
            Q.pop();
    }
    return 0;
}

       注意歩く層数のマークがなければ、極端な状況でiとj層が絶えず歩くことでスーパーメモリになり、5回もスーパーメモリが詰まってしまうことに注意してください.それを徹底的に理解できなかったのは悪い.