Word puzzles are usually simple and very entertaining for all ages. They are so entertaining that Pizza-Hut company started using table covers with word puzzles printed on them, possibly with the intent to minimise their client's perception of any possible delay in bringing them their order.
Even though word puzzles may be entertaining to solve by hand, they may become boring when they get very large. Computers do not yet get bored in solving tasks, therefore we thought you could devise a program to speedup (hopefully!) solution finding in such puzzles.
The following figure illustrates the PizzaHut puzzle. The names of the pizzas to be found in the puzzle are: MARGARITA, ALEMA, BARBECUE, TROPICAL, SUPREMA, LOUISIANA, CHEESEHAM, EUROPA, HAVAIANA, CAMPONESA.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | |
| 0 | Q | W | S | P | I | L | A | A | T | I | R | A | G | R | A | M | Y | K | E | I |
| 1 | A | G | T | R | C | L | Q | A | X | L | P | O | I | J | L | F | V | B | U | Q |
| 2 | T | Q | T | K | A | Z | X | V | M | R | W | A | L | E | M | A | P | K | C | W |
| 3 | L | I | E | A | C | N | K | A | Z | X | K | P | O | T | P | I | Z | C | E | O |
| 4 | F | G | K | L | S | T | C | B | T | R | O | P | I | C | A | L | B | L | B | C |
| 5 | J | E | W | H | J | E | E | W | S | M | L | P | O | E | K | O | R | O | R | A |
| 6 | L | U | P | Q | W | R | N | J | O | A | A | G | J | K | M | U | S | J | A | E |
| 7 | K | R | Q | E | I | O | L | O | A | O | Q | P | R | T | V | I | L | C | B | Z |
| 8 | Q | O | P | U | C | A | J | S | P | P | O | U | T | M | T | S | L | P | S | F |
| 9 | L | P | O | U | Y | T | R | F | G | M | M | L | K | I | U | I | S | X | S | W |
| 10 | W | A | H | C | P | O | I | Y | T | G | A | K | L | M | N | A | H | B | V | A |
| 11 | E | I | A | K | H | P | L | B | G | S | M | C | L | O | G | N | G | J | M | L |
| 12 | L | D | T | I | K | E | N | V | C | S | W | Q | A | Z | U | A | O | E | A | L |
| 13 | H | O | P | L | P | G | E | J | K | M | N | U | T | I | I | O | R | M | N | C |
| 14 | L | O | I | U | F | T | G | S | Q | A | C | A | X | M | O | P | B | E | I | O |
| 15 | Q | O | A | S | D | H | O | P | E | P | N | B | U | Y | U | Y | O | B | X | B |
| 16 | I | O | N | I | A | E | L | O | J | H | S | W | A | S | M | O | U | T | R | K |
| 17 | H | P | O | I | Y | T | J | P | L | N | A | Q | W | D | R | I | B | I | T | G |
| 18 | L | P | O | I | N | U | Y | M | R | T | E | M | P | T | M | L | M | N | B | O |
| 19 | P | A | F | C | O | P | L | H | A | V | A | I | A | N | A | L | B | P | F | S |
Problem
Your task is to produce a program that given the word puzzle and words to be found in the puzzle, determines, for each word, the position of the first letter and its orientation in the puzzle.
You can assume that the left upper corner of the puzzle is the origin, (0,0) . Furthemore, the orientation of the word is marked clockwise starting with letter A for north (note: there are 8 possible directions in total).
Input
The first line of the input contains a number T ≤ 10 which indicates the number of test cases to follow. Each test case starts with a line consisting of three positive numbers: The number of lines of the word puzzle, 0 < L ≤ 1000 , the number of columns, 0 < C ≤ 1000 , and the number of words to be found, 0 < W ≤ 1000 . The following L input lines, each consisting of C uppercase letters, contain the word puzzle. Then at last the W words are input one per line. You can assume that each word can be found exactly once in the word puzzle.
Output
For each test case your program should output W lines: For each word (using the same order as the words were input) print a triplet defining the coordinates, line and column, where the first letter of the word appears, followed by a letter indicating the orientation of the word according to the rules defined above. Each value in the triplet must be separated by one space only.
Print one blank line between test cases.
Example
Input: 1 20 20 10 QWSPILAATIRAGRAMYKEI AGTRCLQAXLPOIJLFVBUQ TQTKAZXVMRWALEMAPKCW LIEACNKAZXKPOTPIZCEO FGKLSTCBTROPICALBLBC JEWHJEEWSMLPOEKORORA LUPQWRNJOAAGJKMUSJAE KRQEIOLOAOQPRTVILCBZ QOPUCAJSPPOUTMTSLPSF LPOUYTRFGMMLKIUISXSW WAHCPOIYTGAKLMNAHBVA EIAKHPLBGSMCLOGNGJML LDTIKENVCSWQAZUAOEAL HOPLPGEJKMNUTIIORMNC LOIUFTGSQACAXMOPBEIO QOASDHOPEPNBUYUYOBXB IONIAELOJHSWASMOUTRK HPOIYTJPLNAQWDRIBITG LPOINUYMRTEMPTMLMNBO PAFCOPLHAVAIANALBPFS MARGARITA ALEMA BARBECUE TROPICAL SUPREMA LOUISIANA CHEESEHAM EUROPA HAVAIANA CAMPONESA Output: 0 15 G 2 11 C 7 18 A 4 8 C 16 13 B 4 15 E 10 3 D 5 1 E 19 7 C 11 11 H
题目思路：其为在一个矩阵中找到字符串的位置，
先用end数组标记字符串类型，然后暴力所有方向的字符串，知道找到为止，
这里暴力时不需考虑字符串重复循环的情况，因为其为寻找单词块，否则会超时。
| Status | Accepted |
|---|---|
| Time | 430ms |
| Memory | 539648kB |
| Length | 4914 |
| Lang | C++ (gcc 6.3) |
| Submitted | 2017-04-11 17:28:27 |
| Shared | |
| RemoteRunId | 19212669 |
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
//int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
typedef struct node{
int x;
int y;
char di;
}NODE;
vector<string> ans;
vector<string> mm;
string s;
const int N = 1e6+5;
const int M = 128;
int n,m,c,T;
NODE used[N];//判断其是否被查找到
class Trie
{
public:
int next[N][M],fail[N],end[N];
int root,L;
int newnode()
{
for(int i = 0;i < M;i++)//每一个节点对应0-128中的任意一个。
next[L][i] = -1;
end[L++] = -1;//表示下面没有节点 初始化，如果是记录次数，就赋0 还可以赋任意的数，
return L-1;
}
void init()
{
L = 0;
root = newnode();
}
void insert(char s[],int id)
{
int len = strlen(s);
int now = root;
for(int i = 0;i < len;i++)
{
if(next[now][s[i]] == -1)
next[now][s[i]] = newnode();
now=next[now][s[i]];
}
end[now]=id;//记录当前匹配单词的节点
//end[now]++;也可以用匹配单词结束后来记录次数
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = 0;i < M;i++)
if(next[root][i] == -1)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
for(int i = 0;i < M;i++)
if(next[now][i] == -1)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
bool query(int x,int y,int di)
{
int now = root;
//memset(used,0,sizeof(used));//初始化used
while(x>=0&&y>=0&&x<n&&y<m)
{
now = next[now][mm[x][y]];
int temp = now;
if(end[temp] != -1)
{
used[end[temp]].x = x-(ans[end[temp]].size()-1)*dir[di][0];
used[end[temp]].y = y-(ans[end[temp]].size()-1)*dir[di][1];
used[end[temp]].di = (char)(di+'A');
}
/* while(temp != root)
{
temp = fail[temp];
}*/
//这里把其注释掉是因为其不包含类似 ”abcd“ 和”ab“ , "abc"这样相互包含的串
x += dir[di][0];
y += dir[di][1];
}
return true;
}
};
char buf1[100];
char buf[2000010];
Trie ac;
int main()
{
scanf("%d",&T);
//ios::sync_with_stdio(false);
while(T--)
{
mm.clear();
ans.clear();
scanf("%d %d %d",&n,&m,&c);
for(int i=0;i<n;i++)
{
scanf("%s",buf1);
s = buf1;
mm.push_back(s);
}
ac.init();
for(int i = 0;i < c;i++)
{
scanf("%s",buf1);
s = buf1;
ans.push_back(s);
ac.insert(buf1,i);
}
ac.build();
//分别暴力求解，枚举所有的串
for(int i=0;i<n;i++)
{
ac.query(i, 0, 1);
ac.query(i, 0, 2);
ac.query(i, 0, 3);
ac.query(i, m-1,5);
ac.query(i, m-1,6);
ac.query(i, m-1,7);
}
//分别暴力求解，枚举所有的串
for (int i = 0; i < m; ++i) {
ac.query(0, i, 3);
ac.query(0, i, 4);
ac.query(0, i, 5);
ac.query(n-1,i ,0);
ac.query(n-1,i ,1);
ac.query(n-1,i ,7);
}
for (int j = 0; j < c; ++j) {
printf("%d %d %c\n",used[j].x,used[j].y,used[j].di);
}
if(T) printf("\n");
}
return 0;
}