1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4  5 #define MAXN 1005 6  7 typedef struct Trie { 8     int v; 9     Trie *next[26];10     Trie() {11         v = 0;12         for (int i=0; i<26; ++i)13             next[i] = NULL;14     }15 } Trie;16 17 Trie root;18 int direct[8][2] = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};19 char map[MAXN][MAXN], buf[MAXN];20 int ans[MAXN][3], n, m, xx, yy;21 bool visit[MAXN];22 23 void create(char str[], int in) {24     int i = 0, id;25     Trie *p = &root, *q;26 27     while (str[i]) {28         id = str[i] - ‘A‘;29         ++i;30         if (p->next[id] == NULL) {31             q = new Trie();32             p->next[id] = q;33         }34         p = p->next[id];35     }36     p->v = in;37 }38 39 void find(Trie *t, int x, int y, int k) {40     if (t == NULL)41         return ;42 43     if (t->v && !visit[t->v]) {44         visit[t->v] = true;45         ans[t->v][0] = xx;46         ans[t->v][1] = yy;47         ans[t->v][2] = k;48     }49     if (x<0 || x>=n || y<0 || y>=m)50         return ;51     find(t->next[map[x][y]-‘A‘], x+direct[k][0], y+direct[k][1], k);52 }53 54 void search() {55     int k;56 57     memset(visit, false, sizeof(visit));58 59     for (xx=0; xx<n; ++xx)60         for (yy=0; yy<m; ++yy)61             for (k=0; k<8; ++k)62                 find(&root, xx, yy, k);63 }64 65 int main() {66     int w;67     int i;68 69     scanf("%d%d%d",&n,&m,&w);70 71     for (i=0; i<n; ++i)72         scanf("%s", map[i]);73 74     for (i=1; i<=w; ++i) {75         scanf("%s", buf);76         create(buf, i);77     }78     search();79     for (i=1; i<=w; ++i)80         printf("%d %d %c\n", ans[i][0], ans[i][1], ans[i][2]+‘A‘);81 82     return 0;83 }