Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Mathematics and Computer Science
String grid
Time Limit: 2000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 5, Accepted users: 1
Problem 10046 : No special judgement
Problem description
  You are given a String grid representing a rectangular grid of letters. You are also given a String find, a word you are to find within the grid. The starting point may be anywhere in the grid. The path may move up, down, left, right, or diagonally from one letter to the next, and may use letters in the grid more than once, but you may not stay on the same cell twice in a row. You are to return an integer indicating the number of ways find can be found within the grid. If the result is more than 1,000,000,000, return -1.

Input
  There will be several test cases. The first line of input is the test case number n. For each case, the first number m between 1 and 50 inclusive means the elements of the grid. The following m lines strings are the statement of the gridí»s element Each element of grid will contain between 1 and 50 uppercase (''A''-''Z'') letters, inclusive. After that, one string is required to be found.

Output
  You should output just one number for each case, meaning the ways found within in the grid.

Sample Input
4
3
ABC
FED
GHI
ABCDEFGHI
3
ABC
FED
GAI
ABCDEA
2
AA
AA
AAAA
5
AAAAA
AAAAA
AAAAA
AAAAA
AAAAA
AAAAAAAAAAA
Sample Output
1
2
108
-1
Problem Source
  HNU Contest 

Submit   Discuss   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:841 today,10600675 total, since 2010-05-07