http://acm.pku.edu.cn/JudgeOnline/problem?id=1204
Код:
#include <stdio.h> #include <string.h> struct Position { int i,j; char orientation; Position(int x, int y, char o) : i(x), j(y), orientation(o) {} }; struct Node { bool wordEnd; Node* child[26]; Position* pos; Node(bool isWordEnd = false, Position* position = NULL) : wordEnd(isWordEnd), pos(position) { for(int i=0; i<26; ++i) child[i] = NULL; } }; char maze[1000][1001];//??? char word[500][1001];//?? void Insert(Node* root, char* s) { char* ps = s; Node* pn = root; while(*ps != '\0') { int index = *ps - 'A'; if(pn->child[index]==NULL) { pn->child[index] = new Node(); if(*(ps+1)=='\0') pn->child[index]->wordEnd = true; } pn = pn->child[index]; ++ps; } } Node* Find(Node* root, char* s) { char* ps = s; Node* pn = root; while(*ps != '\0') { int index = *ps - 'A'; if(pn->child[index]==NULL) return NULL; pn = pn->child[index]; ++ps; } if(pn!=NULL && pn->wordEnd) return pn; return NULL; } inline Node* PortionFind(Node* startFindNode, char c) { return startFindNode->child[c-'A']; } int deltai[]={-1,-1,0,1,1,1,0,-1}; int deltaj[]={0,1,1,1,0,-1,-1,-1}; int L,C,W,i,j,k,len,maxlen=0; char test[1001]; int cnt = 0; inline bool valid(int i, int j) { return (i>=0)&&(j>=0)&&(i<L)&&(j<C); } int main() { Node *root = new Node(); scanf("%d%d%d",&L,&C,&W); for(i=0; i<L; ++i) scanf("%s",maze[i]); for(i=0; i<W; ++i) { scanf("%s",word[i]); len = strlen(word[i]); if(len>maxlen) maxlen = len; Insert(root,word[i]); } for(i=0; i<L; ++i) { for(j=0; j<C; ++j) { for(k=0; k<8; ++k)//???? { int l = 1; int x = i; int y = j; Node *startNode = root; while(l<=maxlen && valid(x,y)) { test[l-1] = maze[x][y]; test[l]='\0'; Node* pNode = PortionFind(startNode,test[l-1]); if(pNode==NULL) break; if(pNode->wordEnd && pNode->pos==NULL) { pNode->pos = new Position(i,j,'A'+k); cnt++; if(cnt==W) goto PRINT; } ++l; x += deltai[k]; y += deltaj[k]; startNode = pNode; } } } } PRINT: for(i=0; i<W; ++i) { Node* pNode = Find(root,word[i]); printf("%d %d %c\n", pNode->pos->i, pNode->pos->j, pNode->pos->orientation); } return 0; }