1218: [动态规划]words牛的单词[Piele, 1987]

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:13 Solved:6

Description

奶牛们得到了一本找单词的书,里面有各种字迷例如:

       H A F B T H E W

       J B S Y O Y J S

       L G B E S T Y U

       T S C O L T E D

       J T F S D O W L

W T S E T N O C

例如目标是找单词BEST或是CONTEST。你可以在第三行找到BEST在第最后一行找到CONTEST

L G>B*E*S*T

T*S*E*T*N*O*C<

单词可以从任何字符出发,沿上下左右或是对角线方向寻找。

你的目标是帮助奶牛们找到更难的单词。给出一个N* M行的字符表格(3<=N<=80,3<=M<=50)和一个藏在其中的单词,找到它并告诉奶牛们它的位置。

Input

1行:两个空格隔开的整数:NM

2行:要寻找的单词(大写)

3M+2行:每行N个字母(都是大写)。

 

Output

1行:两个只用一个空格隔开的整数:单词的第一个字母在表格中的行和列。

2行:这个单词的剩余部分相对于第一个字母的方向。如果第一个字母是x,不同的方向如下图所示:

                     NW   N   NE

                      W   x   E

                     SW   S   SE

 

Sample Input Copy

8 6
CONTEST
HAFBTHEW
JBSYOYJS
LGBESTYU
TSCOLTED
JTFSDOWL
WTSETNOC

Sample Output Copy

6 8
W

Source/Category