学步园

//   url: http://acm.hdu.edu.cn/showproblem.php?pid=1671
//   该题目也主要是字典树问题，就是看里面的某一个字符串是否完全属于另一个字符串，如果有的话输出no（无法拨打电话），否则就是yes
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;
typedef struct isTree
{
    int v;
    isTree *next[10];
}isTree;
    isTree root;
void isCreatTree(char *s)
{
    int len,i,j,id;
    isTree *p=&root,*q;
    len=strlen(s);
    for(i=0;i<len;i++)
    {
        id=s[i]-'0';
        if(p->next[id]==NULL)
        {
            q=(isTree *)malloc(sizeof(root));
            q->v=1;
            for(j=0;j<10;j++)
              q->next[j]=NULL;
             p->next[id]=q;
             p=p->next[id];
        }
        else
        {
            p->next[id]->v++;
            p=p->next[id];
        }
    }
    p->v=-1;
    //   经过自己的调试再加上对代码的理解，p->v是一个至关重要的控制节点
    //  构建最后一个节点完成之后，赋值为-1，就说明到达了结束的地方
    //    这里要说一句，最后面的p->=-1  和前面的p->next[id]->v++  两者之家没有必然的联系，
    //  这个=-1的事在for语句完全结束之后最后面加上去的，并不会对前面的v++产生任何的影响
    //   举个例子吧，如911  和978
    //   第一个构建好树之后，第二个也开始构建了，由于第一个数字是9，所以第一步判断p->next[id]!=null
    //   因此会进入else里面，v++；   但是到第二个数字就不再是1了而是7，就变成null了，
    //    此时的p->v和上次的p->v 是两个完全不同的节点,p->v++  就是一个分支的节点数  就如上面的例子 当步运行到978厘米的9后发现v=2了，和明显就是分了两个分支1和7
}
int isFindTree(char *s)
{
    int len,i,j,id;
    isTree *p=&root;
    len=strlen(s);
    for(i=0;i<len;i++)
    {
        id=s[i]-'0';
        p=p->next[id];
        if(p==NULL)
           return 0;     //    说明此次查找的字符串没在前面所有的字符串中出现过
        if(p->v==-1)
           return -1;
           //  既然p->next[id]->v=-1  则说明该字符串的一部分已经在前面的某个字符串里面重复了就如
           //  已经构建了1234  现在需要查找的是12345，到5了p->v==-1 而这样的要求也是满足题意的
           //  则，也需要输出答案
    }
    return -1;
    //  意思和上面的一样  只是先发现12345  后发现1234  就这样的区别
}
int isDelTree(isTree *T)
{
    int i;
    if(T==NULL)
        return 0;
    for(i=0;i<10;i++)
    {
        if(T->next[i]!=NULL)
          isDelTree(T->next[i]);
    }
    free(T);
    return 0;
}
int main()
{
    int t,n,i,j;
    char str[15];
    while(scanf("%d",&t)!=EOF && t!=0)
    {
        while(t--)
        {
            j=0;
            for(i=0;i<10;i++)
              root.next[i]=NULL;
             scanf("%d",&n);
             while(n--)
             {
                 scanf("%s",str);
                 if(isFindTree(str)==-1) //  说明找到了,解释如上
                    j=1;
                 if(j==1)
                    continue;
                 isCreatTree(str);
             }
             if(j==1)
                printf("NO\n");
             else
                printf("YES\n");
             isDelTree(&root);
        }
    }
    return 0;
}