2787. spell the word

单点时限: 2.0 sec

内存限制: 256 MB

You are playing a game with a NxN grid of letters. The goal of the game is to spell out a N-letter word somewhere on the grid either horizontally from left to right or vertically from top to bottom. To achieve this, you will perform a series of moves. On each move, you can swap either two rows or two columns of the grid.

You are given a String[] grid containing the initial state of the grid. The j-th character of the i-th element of grid is the letter at row i, column j. The word you must spell is given to you in the String word. All letters in word are distinct. Note that lowercase and uppercase versions of the same letter are considered different in this problem, so ‘A’ and ‘a’ are distinct. Print the minimal number of moves required to spell the given word on the grid, or -1 if it is impossible.

note:

word will contain between 1 and 50 letters (‘a’-‘z’, ‘A’-‘Z’), inclusive.

All characters in word will be distinct.

The number of elements in grid will be equal to the length of word.

The length of each element of grid will be equal to the length of word.

Each element of grid will contain only letters (‘a’-‘z’, ‘A’-‘Z’).

输入格式

The first line of input gives the number of cases, N(1 ≤ N ≤ 120). N test cases follow.

Each test case consists of one integers n which represents the size of grid of letters, n lines with n characters represents each element of grid , and a line represents the word.

输出格式

Print the minimal number of moves required to spell the given word on the grid, or -1 if it is impossible.

样例

Input
3
2
Mu
uM
Mu
3
sdf
bca
hgf
abc
3
cdf
bca
agf
abc
Output
0
2
1

5 人解决,13 人已尝试。

7 份提交通过,共有 22 份提交。

8.1 EMB 奖励。

创建: 10 年,2 月前.

修改: 2 年,6 月前.

最后提交: 7 年,9 月前.

来源: ECNU 2009 ACM selective trial From TopCoder

题目标签