HDOJ 1181変形課深搜回溯

変形レッスンTime Limit:2000/1000 MS(Java/others)Memory Limit:131072/65536 K(Java/others)Total Submission(s):18474 Accepted Submission(s):6663
Problem Descriptionえ......変形の授業でHarryは少しトラブルに遭遇しました.彼はHermioneのようにすべての呪文を覚えることができないので、勝手に野球をハリネズミに変えることができますが、彼は変形呪文の統一的な法則を発見しました.もし呪文がaで始まるbで終わる単語であれば、ハーリーはすでに彼のできるすべての呪文を1つの表に並べて、彼はあなたに先生の宿題を完成できるかどうかを計算してもらいたいと思って、1つのB(ball)を1つのM(Mouse)に変えて、あなたは知っていて、もし彼が自分で完成できないならば、彼はHermioneに教えてもらうしかなくて、しかもたくさんのよく勉強する道理を聞かなければなりません.
Inputテストデータは複数組あります.各グループには複数の行があり、各行に1つの単語があり、小文字のみを含み、Harryができるすべての呪文である.数字0は入力の終わりを表す.
Outputハリーが彼の宿題を完成できれば「Yes.」を出力し、そうでなければ「No.」(無視しない句号)を出力する.
Sample Input so soon river goes them got moon begin big 0
Sample Output Yes.
HintHint Harryはこの呪文を唱えることができます:“big-got-them”.
このコードはまだ理解しやすいですが、古典的なDFSはタイムアウトしていません.私は意外にもmからbへ検索しました.

#include<stdlib.h>
#include<stdio.h>
#include <string.h>
using namespace std;
char a[1000][50];
int len[1000];
int k;int flag;
bool vis[1000];
void dfs(char x)
{
    if(x=='b')
        {
            flag=1;
            return ;
        }
    if(flag==1)
    {
        return;
    }
    for(int i=0;i<k;i++)
    {
        //printf("vis[%d]=%d
",i,vis[i]);
        if(vis[i]==0)
        {
            if(a[i][len[i]]==x)
            {
   // printf("a[%d][%d]=%c
",i,len[i],a[i][len[i]]);
                vis[i]=1;
               // printf("x=%c
",x);
                dfs(a[i][0]);
               // printf("x=%c
",x);
                vis[i]=0;
            }
        }
    }
}
int main()
{
    while(scanf("%s",a[0])!=EOF)
    {
        flag=0;
         int i=0;
        if(a[0][0]=='0')
        {
            printf("no.
");
            continue;
        }
        memset(vis,0,sizeof(vis));
        while(a[i][0]!='0')
        {
            len[i]=strlen(a[i])-1;
            i++;
            scanf("%s",a[i]);
        }
        k=i;
        dfs('m');
        if(flag==1)
            printf("Yes.
");
        else
            printf("No.
");

    }
}

次のコードはbからmへ検索され、差は多くありません.

#include<stdlib.h>
#include<stdio.h>
#include <string.h>
using namespace std;
char a[1000][50];
int len[1000];
int k;int flag;
bool vis[1000];
void dfs(char x)
{
    if(x=='m')
        {
            flag=1;
            return ;
        }
    if(flag==1)
    {
        return;
    }
    for(int i=0;i<k;i++)
    {
        //printf("vis[%d]=%d
",i,vis[i]);
        if(vis[i]==0)
        {
            if(a[i][0]==x)
            {
               // printf("a[%d][%d]=%c
",i,len[i],a[i][len[i]]);
                vis[i]=1;
               // printf("x=%c
",x);
                dfs(a[i][len[i]]);
               // printf("x=%c
",x);
                vis[i]=0;
            }
        }
    }
}
int main()
{
    while(scanf("%s",a[0])!=EOF)
    {
        flag=0;
         int i=0;
        if(a[0][0]=='0')
        {
            printf("no.
");
            continue;
        }
        memset(vis,0,sizeof(vis));
        while(a[i][0]!='0')
        {
            len[i]=strlen(a[i])-1;
            i++;
            scanf("%s",a[i]);
        }
        k=i;
        dfs('b');
        if(flag==1)
            printf("Yes.
");
        else
            printf("No.
");

    }
}