poj 1204 Word Puzzles

题目来源：http://poj.org/problem?id=1204

题意：给你一个矩阵，矩阵里面存放着一些字符，问给出的字符串，是否在矩阵中，并判断在该字符串的首个字符在矩阵中的位置，以及该字符串的方向(可以看一下样例，就明白了).

正北标记为'A'，东北标记为'B',类似以顺时针并按字典序标记方向，即到'H'表示西北方向。

ac自动机来做的，事实上，这个题还可以利用深搜来求解。

ac自动机比较好的参考资料：http://download.csdn.net/detail/hearthougan/7316089

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int MAXN = 1010;struct Trie_Node
{int index;Trie_Node* pNext[26];Trie_Node* pFail;Trie_Node(){index = 0;memset(pNext, NULL, sizeof(pNext));pFail = NULL;}
};Trie_Node* pRoot;
Trie_Node* Q[MAXN*100];
char Graph[MAXN][MAXN];
int row, col;int dir[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};//这一块需要注意，数组的方向跟实际坐标的方向是不一样的
int Len[MAXN], res[MAXN][3];bool IsCanGo(int x, int y)
{if(x < 0 || x >= row || y < 0 || y >= col)return false;return true;
}void Build_Trie(char* str, int id)//建立字典树
{int j, i = 0;Trie_Node* p = pRoot;while(str[i]){j = str[i++] - 'A';if(p->pNext[j] == NULL)p->pNext[j] = new Trie_Node;p = p->pNext[j];}p->index = id;
}void Build_Fail()//建立失败指针
{Trie_Node* tmp;Trie_Node* p;int qs = 0, qe = 0, i;Q[qe++] = pRoot;pRoot->pFail = NULL;while(qs < qe){tmp = Q[qs++];p = NULL;for(i = 0; i < 26; ++i){if(tmp->pNext[i] != NULL){if(tmp == pRoot)tmp->pNext[i]->pFail = pRoot;else{p = tmp->pFail;while(p != NULL){if(p->pNext[i] != NULL){tmp->pNext[i]->pFail = p->pNext[i];break;}p = p->pFail;}if(p == NULL)tmp->pNext[i]->pFail = pRoot;}Q[qe++] = tmp->pNext[i];}}}
}void Query_Trie(int x, int y, int d)//查询
{int j;Trie_Node* p = pRoot;Trie_Node* tmp;while(IsCanGo(x, y))//多模同时匹配{j = Graph[x][y] - 'A';while(p->pNext[j] == NULL && p != pRoot)//如果p是指向叶子节点，那么就找他的失败指针指向的结点p = p->pFail;p = p->pNext[j] == NULL ? pRoot : p->pNext[j];tmp = p;//所谓多模同时匹配，关键点就是在这里,每到达一个节点,就查看它的失败指针指向的节点,是否也是一个单词的结尾while(tmp != pRoot && tmp->index > 0){res[tmp->index][0] = x - Len[tmp->index]*dir[d][0];//模式串所在位置的横、纵坐标res[tmp->index][1] = y - Len[tmp->index]*dir[d][1];res[tmp->index][2] = d;//搜寻的方向tmp->index = 0;tmp = tmp->pFail;}x = x + dir[d][0];y = y + dir[d][1];}
}void Delete_Trie(Trie_Node* p)
{int i;Trie_Node* tmp = p;for(i = 0; i < 26; ++i)if(tmp->pNext[i])Delete_Trie(tmp->pNext[i]);delete tmp;
}int main()
{int subnum, i, j;char str[MAXN];while(~scanf("%d %d %d", &row, &col, &subnum)){pRoot = new Trie_Node;memset(res, 0, sizeof(res));for(i = 0; i < row; ++i)scanf("%s", Graph[i]);for(i = 1; i <= subnum; ++i){scanf("%s", str);Len[i] = strlen(str)-1;Build_Trie(str, i);}Build_Fail();for(i = 0; i < row; ++i)//按每一行的字符串进行匹配{for(j = 0; j < 8; ++j){Query_Trie(i, 0, j);//正着扫一下Query_Trie(i, col-1, j);//反着扫一下}}for(i = 0; i < col; ++i){for(j = 0; j < 8; ++j){Query_Trie(0, i, j);Query_Trie(row-1, i, j);}}for(i = 1; i <= subnum; ++i)printf("%d %d %c\n", res[i][0], res[i][1], res[i][2]+'A');Delete_Trie(pRoot);}return 0;
}