【POJ】1204 Word Puzzles

这道题目各种wa。首先是错了一个坐标，居然没测出来。然后是剪枝错误。搜索pen时就返回，可能还存在串pen*。

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #define MAXN 1005

 typedef struct Trie {

     int v;

     Trie *next[];

     Trie() {

         v = ;

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

             next[i] = NULL;

     }

 } Trie;

 Trie root;

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

 char map[MAXN][MAXN], buf[MAXN];

 int ans[MAXN][], n, m, xx, yy;

 bool visit[MAXN];

 void create(char str[], int in) {

     int i = , id;

     Trie *p = &root, *q;

     while (str[i]) {

         id = str[i] - 'A';

         ++i;

         if (p->next[id] == NULL) {

             q = new Trie();

             p->next[id] = q;

         }

         p = p->next[id];

     }

     p->v = in;

 }

 void find(Trie *t, int x, int y, int k) {

     if (t == NULL)

         return ;

     if (t->v && !visit[t->v]) {

         visit[t->v] = true;

         ans[t->v][] = xx;

         ans[t->v][] = yy;

         ans[t->v][] = k;

     }

     if (x< || x>=n || y< || y>=m)

         return ;

     find(t->next[map[x][y]-'A'], x+direct[k][], y+direct[k][], k);

 }

 void search() {

     int k;

     memset(visit, false, sizeof(visit));

     for (xx=; xx<n; ++xx)

         for (yy=; yy<m; ++yy)

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

                 find(&root, xx, yy, k);

 }

 int main() {

     int w;

     int i;

     scanf("%d%d%d",&n,&m,&w);

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

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

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

         scanf("%s", buf);

         create(buf, i);

     }

     search();

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

         printf("%d %d %c\n", ans[i][], ans[i][], ans[i][]+'A');

     return ;

 }