Informatica Online Judge

  격자 읽기 [0381 / 017D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 60   Total Tried : 544


The Champion of this Problem (C++) : tlsdydaud1 - 0ms / 424byte
My Best Submission (C++) : N/A

[]

Background

아래와 같은 격자판을 보자.



위 격자판에서 TARTU를 읽는 방법의 수는 7가지가 있다.



문자 격자판과 단어가 주어질 때 그 단어를 읽는 방법의 수를 구하는 프로그램을 작성하시오. 단, 첫 번째 문자는 격자판의 어느 부분에서 시작해도 관계없다. 그 다음 문자 부터는 이전 문자와 가로, 세로, 대각선으로 연결된 것들만 읽을 수 있다.

Input

첫 번째 줄에 3개의 정수가 입력된다. 첫 번째 값은 H로 격자판의 높이를 의미한다. 두 번 째값은 W로 격자판의 폭을 의미한다. 그리고 마지막 값은 L로 입력되는 단어의 길이를 의미한다. 다음 줄 부터 H행에 걸쳐서 W개의 길이 격자판에 들어갈 문자들이 입력된다.
마지막 줄에는 찾아야할 단어가 L의 길이로 입력된다.
(단, 모든 문자는 영문자 대문자이다.)

[입력값의 정의역]
1<= H, W <= 200
1 <= L <= 20

[Sub-Task Info]
#1 : H, W = 5, L = 10
#2 : H, W = 200, L = 5
#3, #4 : H, W = 50, L = 20

Output

읽을 수 있는 경우의 수를 정수로 출력한다. 단 답은 항상 1018를 넘지 않는다.

IO Example

예시 1>

입력
3 4 5
ERAT
ATSR
AUTU
TARTU

출력
7

예시 2>

입력
2 2 10
AA
AA
AAAAAAAAAA

출력
78732

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]