Preparing NOJ

D. 寻找单词

10000ms 65536K

Description:

    给出一个n×m的棋盘,棋盘的每个格子里都填了一个字母,另外给一份单词表,要求在棋盘中找出每一个可以被找到的单词的位置。
    单词必须和棋盘中一条不间断的直线匹配,大小写不敏感(即大写字母和相应的小写字母被认为是相同的)。这条直线可以使水平、竖直、对角线的八个方向之一。

Input:

    第一行包含一个正整数T(T≤1000),表示样例个数,接下来给出T组测试用例。
    每组测试用例包含多行,第一行有两个正整数n和m(1≤n, m≤100)。接下来n行每行有m个字母,即一个包含且只包含字母的棋盘。下一行只有一个整数k(1≤k≤50)。接下来k行是待查找的单词,每行一个。这些单词也只包含字母,不包含空格、连字符或者其他非字母字符。

Output:

    每组测试用例输出k行。每行输出两个正整数,对应表示第k个单词在棋盘中的起始位置,这一对整数以一个空格隔开。第一个数代表这个单词首字母的行号(最上方为第1行),第二个数代表这个单词首字母的列号(最左边为第1列)。如果一个单词在棋盘中不止出现一次,则输出首字母位置最靠上的那一个,如果仍有多解,则输出这些解中最靠左侧的那一个。如果单词未被找到,则输出-1 -1。
    输出时相邻两组数据之间用一个空行隔开。

Sample Input:

1
8 11
abcDEFGhigg
hEbkWalDork
FtyAwaldORm
FtsimrLqsrc
byoArBeDeyv
Klcbqwikomk
strEBGadhrb
yUiqlxcnBjf
4
Waldorf
Bambi
Betty
Dagbert

Sample Output:

2 5
2 3
1 2
7 8

Note:

    由于排版问题,样例输入的棋盘列未能很好的对齐,但在数位编辑器里,行列是严格对齐的,也即棋盘是个标准的矩阵。

本题由旧版NOJ导入,来源:ACM爱好者协会

Info

NOJ

Provider NOJ

Code NOJ1850

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet