시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB49120318146.173%

문제

다음과 같은 단어 격자가 있다.

여기서 TARTU란 단어를 읽는 방법은 총 7가지가 있다.

단어 격자와, 단어가 주어졌을 때, 주어진 단어를 읽을 수 있는 방법의 경우의 수를 구하는 프로그램을 작성하시오. 단어의 첫 글자는 격자의 어느 곳이 되어도 되고, 두 번째 글자부터는 그 전 글자가 있던 칸과 인접한 칸이어야 한다. (상하좌우, 대각선, 총 8방향). 각 칸은 중복되게 사용해도 된다.

입력

첫째 줄에 3개의 수 H, W, L이 주어진다. H는 격자의 높이, W는 격자의 격자의 너비, L은 단어의 길이이다. (1<=H,W<=200, 1<=L<=100) 다음 줄 부터 H개의 줄에는 격자에 있는 글자가 W개씩 주어지고, 마지막 줄에는 길이가 L인 단어가 주어진다. 모든 글자는 알파벳 대문자이다.

출력

단어를 읽을 수 있는 방법의 경우의 수를 출력한다. 이 값은 1018을 넘지 않는다.

예제 입력 1

3 4 5
ERAT
ATSR
AUTU
TARTU

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjI0MTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWM1YjQgXHVhY2E5XHVjNzkwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YjJlOFx1YzViNCBcdWFjYTlcdWM3OTBcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA1XC9TY3JlZW4gc2hvdCAyMDExLTA1LTEwIGF0IDEyXzE0XzAzIEFNLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjgxcHg7IHdpZHRoOjEzN3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YWUzMFx1YzExYyBUQVJUVVx1Yjc4MCBcdWIyZThcdWM1YjRcdWI5N2MgXHVjNzdkXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWNkMWQgN1x1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDExMDVcL1NjcmVlbiBzaG90IDIwMTEtMDUtMTAgYXQgMTJfMTRfNDYgQU0ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTQ0cHg7IHdpZHRoOjU4OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YjJlOFx1YzViNCBcdWFjYTlcdWM3OTBcdWM2NDAsIFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc3ZFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWIyZThcdWM1YjRcdWM3NTggXHVjY2FiIFx1YWUwMFx1Yzc5MFx1YjI5NCBcdWFjYTlcdWM3OTBcdWM3NTggXHVjNWI0XHViMjkwIFx1YWNmM1x1Yzc3NCBcdWI0MThcdWM1YjRcdWIzYzQgXHViNDE4XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YWUwMFx1Yzc5MFx1YmQ4MFx1ZDEzMFx1YjI5NCBcdWFkZjggXHVjODA0IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWM3ODhcdWIzNTggXHVjZTc4XHVhY2ZjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWNlNzhcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiAoXHVjMGMxXHVkNTU4XHVjODhjXHVjNmIwLCBcdWIzMDBcdWFjMDFcdWMxMjAsIFx1Y2QxZCA4XHViYzI5XHVkNWE1KS4gXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWM5MTFcdWJjZjVcdWI0MThcdWFjOGMgXHVjMGFjXHVjNmE5XHVkNTc0XHViM2M0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgM1x1YWMxY1x1Yzc1OCBcdWMyMTggSCwgVywgTFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIEhcdWIyOTQgXHVhY2E5XHVjNzkwXHVjNzU4IFx1YjE5Mlx1Yzc3NCwgV1x1YjI5NCBcdWFjYTlcdWM3OTBcdWM3NTggXHVhY2E5XHVjNzkwXHVjNzU4IFx1YjEwOFx1YmU0NCwgTFx1Yzc0MCBcdWIyZThcdWM1YjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc0XHViMmU0LiAoMSZsdDs9SCxXJmx0Oz0yMDAsIDEmbHQ7PUwmbHQ7PTEwMCkgXHViMmU0XHVjNzRjIFx1YzkwNCBcdWJkODBcdWQxMzAgSFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2E5XHVjNzkwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFlMDBcdWM3OTBcdWFjMDAgV1x1YWMxY1x1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIExcdWM3NzggXHViMmU4XHVjNWI0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YWUwMFx1Yzc5MFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjJlOFx1YzViNFx1Yjk3YyBcdWM3N2RcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjMTJcdWM3NDAgMTA8c3VwPjE4PFwvc3VwPlx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI0MTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMZXR0ZXIgR3JpZCIsImRlc2NyaXB0aW9uIjoiPHA+Q29uc2lkZXIgdGhlIGZvbGxvd2luZyBsZXR0ZXIgZ3JpZDo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTEwNVwvU2NyZWVuIHNob3QgMjAxMS0wNS0xMCBhdCAxMl8xNF8wMyBBTS5wbmdcIiBzdHlsZT1cImhlaWdodDo4MXB4OyB3aWR0aDoxMzdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgNyB3YXlzIHRvIHJlYWQgdGhlIHdvcmQgVEFSVFUgZnJvbSB0aGUgZ3JpZDo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTEwNVwvU2NyZWVuIHNob3QgMjAxMS0wNS0xMCBhdCAxMl8xNF80NiBBTS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNDRweDsgd2lkdGg6NTg4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBsZXR0ZXIgZ3JpZCBhbmQgYSB3b3JkLCB5b3VyIHRhc2sgaXMgdG8gZGV0ZXJtaW5lIHRoZSBudW1iZXIgb2Ygd2F5cyB0aGUgd29yZCBjYW4gYmUgcmVhZCBmcm9tIHRoZSBncmlkLiBUaGUgXHVmYjAxcnN0IGxldHRlciBvZiB0aGUgd29yZCBjYW4gYmUgaW4gYW55IGNlbGwgb2YgdGhlIGdyaWQsIGFuZCBhZnRlciBlYWNoIGxldHRlciwgdGhlIG5leHQgbGV0dGVyIGhhcyB0byBiZSBpbiBvbmUgb2YgdGhlIG5laWdoYm91ciBjZWxscyAoaG9yaXpvbnRhbGx5LCB2ZXJ0aWNhbGx5IG9yIGRpYWdvbmFsbHkpLiBBIGNlbGwgY2FuIGJlIHVzZWQgbXVsdGlwbGUgdGltZXMgd2hlbiByZWFkaW5nIHRoZSB3b3JkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBcdWZiMDFsZSBncmlkLmluIGNvbnRhaW5zIHRocmVlIGludGVnZXJzOiBIICgxICZsZTsgSCAmbGU7IDIwMCksIHRoZSBoZWlnaHQgb2YgdGhlIGdyaWQsIFcgKDEgJmxlOyBXICZsZTsgMjAwKSwgdGhlIHdpZHRoIG9mIHRoZSBncmlkLCBhbmQgTCAoMSAmbGU7IEwgJmxlOyAxMDApLCB0aGUgbGVuZ3RoIG9mIHRoZSB3b3JkLiBUaGUgZm9sbG93aW5nIEggbGluZXMgZWFjaCBjb250YWluaW5nIFcgbGV0dGVycyBkZXNjcmliZSB0aGUgZ3JpZC4gVGhlIGxhc3QgbGluZSBjb250YWluaW5nIEwgbGV0dGVycyBkZXNjcmliZXMgdGhlIHdvcmQuIEFsbCBsZXR0ZXJzIGluIHRoZSBncmlkIGFuZCBpbiB0aGUgd29yZCBhcmUgdXBwZXJjYXNlIEVuZ2xpc2ggbGV0dGVycyAoQS4gLiAuIFopLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2YgdGhlIFx1ZmIwMWxlIGdyaWQub3V0IHNob3VsZCBjb250YWluIG9uZSBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIHdheXMgdGhlIHdvcmQgY2FuIGJlIHJlYWQgZnJvbSB0aGUgZ3JpZC4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGUgYW5zd2VyIGlzIGFsd2F5cyBhdCBtb3N0IDEwPHN1cD4xODxcL3N1cD4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2010 P1번