GCPC 2013_A Boggle DFS+字典树 CSU 1457

上周比赛的题目，由于那个B题被神编译器的优化功能给卡了，就没动过这个题，其实就是个字典树嘛。当然，由于要在Boggle矩阵里得到初始序列，我还一度有点虚，不知道是用BFS还是DFS，最后发现DFS要好一些，但是会不会超时呢，我就先敲了DFS部分，先在DFS里面输出所有情况，发现总共搜完只有24W+的情况，然后字典树的匹配几乎是常数时间（因为字符串最大长度只有8）。。。所以就试着做了一下，WA了几次，发现是数组开小了，好久没做字典树的题，我只开了节点个数目的数组，这肯定不对啊，最大可能是30W（字符串总数） *8（同上），当然实际也不会打得这么离谱，因为总共才26个字母，重合的几率很大，所以最多开个30W*2其实就够了。

今天敲字典树之后突然有种想法，发现以前敲这个都是对着模板敲，现在感觉对这个算法已经很理解了，所以我随便自己怎么发挥，没用结构体，没用指针，照样很好的实现了。

像AC自动机我还是不是特别熟练，但是我觉得再照模板敲肯定学得更慢，学算法，真的不要学形，而是要学神。

这个题目也有用AC自动机处理的，确实可以优化一些，失败的话，对应DFS回退，然后树上是对应失败节点，不过处理起来要复杂一些。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

char mat[][];

char wlist[][];

int vis[];

int w,n,inq[][];

char rec[];

int dir[][]={{,},{,},{,-},{-,},{,},{,-},{-,-},{-,}};

int cnt,ch[][],val[],ids[];

int point[]={,,,,,,,,,,};

int ans_num,ans_point;

char anschar[];

void inserts(char* s,int num)

{

    int rt=;

    int len=strlen(s);

    for (int i=;i<len;i++){

        int k=s[i]-'A';

        if (ch[rt][k]==-){

            ch[rt][k]=cnt++;

        }

        rt=ch[rt][k];

    }

    val[rt]=point[len];

    ids[rt]=num;

}

void solve(char* s)

{

    int rt=;

    int len=strlen(s);

    for (int i=;i<len;i++){

        int k=s[i]-'A';

        if (ch[rt][k]==-) break;

        rt=ch[rt][k];

    }

    if (val[rt]!=- && vis[ids[rt]]==){

        vis[ids[rt]]=;

        ans_num++;

        ans_point+=val[rt];

        if (ans_num==)

            memcpy(anschar,s,);

        else if (len==strlen(anschar) && strcmp(s,anschar)<)

            memcpy(anschar,s,);

        else if (len>strlen(anschar))

            memcpy(anschar,s,);

    }

}

void dfs(int x,int y,int d)

{

    if (d>) return;

    rec[d-]=mat[x][y];

    rec[d]='\0';

    solve(rec);

    inq[x][y]=;

    int tmp;

    for (int i=;i<;i++){

        int nx=x+dir[i][];

        int ny=y+dir[i][];

        if (nx< || ny< || nx>= || ny>=) continue;

        if (inq[nx][ny]) continue;

        inq[nx][ny]=;

        dfs(nx,ny,d+);

        inq[nx][ny]=;

    }

    inq[x][y]=;

}

int main()

{

    //freopen("rand.in","r",stdin);

    //freopen("rand.out","w",stdout);

    while (scanf("%d",&w)!=EOF)

    {

        memset(ch,-,sizeof ch);

        memset(val,-,sizeof val);

        memset(ids,-,sizeof ids);

        cnt=;

        for (int i=;i<w;i++){

            scanf("%s",wlist[i]);

            inserts(wlist[i],i);

        }

        scanf("%d",&n);

        for (int i=;i<n;i++){

            memset(vis,,sizeof vis);

            ans_num=ans_point=;

            for (int j=;j<;j++) {scanf("%s",mat[j]);}

            for (int q=;q<;q++)

             for (int k=;k<;k++){

                    dfs(q,k,);

            }

            printf("%d %s %d\n",ans_point,anschar,ans_num);

        }

    }

    return ;

}