All submissions for this problem are available.
Magazines and newspapers often have letter matrices in which certain words need to be located. Umesh, a puzzle fanatic at IIT Roorkee, had an idea for a new kind of searching puzzle. In the letter matrix provided, words can be located along any set of diagonals, with repetition of past selected letters.
For example, in the letter matrix:
B X A X X X A X X X X B B X X X A X A X X X B X X
The string ABA can be found in 14 different ways – corresponding to the following locations:
A B A (1,1) (0,0) (1,1) (1,1) (2,2) (3,1) (1,1) (2,2) (3,3) (1,1) (2,2) (1,1) (3,1) (2,2) (3,1) (3,1) (2,2) (3,3) (3,1) (4,2) (3,1) (3,1) (4,2) (3,3) (3,1) (2,2) (1,1) (3,3) (2,2) (3,3) (3,3) (2,2) (1,1) (3,3) (2,2) (3,1) (3,3) (4,2) (3,1) (3,3) (4,2) (3,3)
So, given a matrix of size NxN, you need to find out the total number of locations of a particular string. The input and output formats are as follows:
Line 1: N. 1 <= N <= 1000
Line 2 to N+1: Elements of the NxN matrix in row major order (separated by a space)
Line N+2: The string to search. Maximum length of this string will be N2.
Line 1: The number of ways in which the string can be found in the matrix.
Input: 8 B X A X X X A X X X X B B X X X A X A X X X B X X ABA Output: 14
|Time Limit:||0.4 - 1.4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TEXT|
Fetching successful submissions
If you are still having problems, see a sample solution here.