시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 149 61 58 47.934%

문제

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

여기서 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+PFwvcD5cclxuXHJcbjxwPlx1YjJlOFx1YzViNCBcdWFjYTlcdWM3OTBcdWM2NDAsIFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc3ZFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWIyZThcdWM1YjRcdWM3NTggXHVjY2FiIFx1YWUwMFx1Yzc5MFx1YjI5NCBcdWFjYTlcdWM3OTBcdWM3NTggXHVjNWI0XHViMjkwIFx1YWNmM1x1Yzc3NCBcdWI0MThcdWM1YjRcdWIzYzQgXHViNDE4XHVhY2UwLCBcdWI0NTBcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHViZDgwXHVkMTMwXHViMjk0IFx1YWRmOCBcdWM4MDQgXHVhZTAwXHVjNzkwXHVhYzAwIFx1Yzc4OFx1YjM1OCBcdWNlNzhcdWFjZmMgXHVjNzc4XHVjODExXHVkNTVjIFx1Y2U3OFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIChcdWMwYzFcdWQ1NThcdWM4OGNcdWM2YjAsIFx1YjMwMFx1YWMwMVx1YzEyMCwgXHVjZDFkIDhcdWJjMjlcdWQ1YTUpLiBcdWFjMDEgXHVjZTc4XHVjNzQwIFx1YzkxMVx1YmNmNVx1YjQxOFx1YWM4YyBcdWMwYWNcdWM2YTlcdWQ1NzRcdWIzYzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCAzXHVhYzFjXHVjNzU4IFx1YzIxOCBILCBXLCBMXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gSFx1YjI5NCBcdWFjYTlcdWM3OTBcdWM3NTggXHViMTkyXHVjNzc0LCBXXHViMjk0IFx1YWNhOVx1Yzc5MFx1Yzc1OCBcdWFjYTlcdWM3OTBcdWM3NTggXHViMTA4XHViZTQ0LCBMXHVjNzQwIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NzRcdWIyZTQuICgxJmx0Oz1ILFcmbHQ7PTIwMCwgMSZsdDs9TCZsdDs9MTAwKSBcdWIyZTRcdWM3NGMgXHVjOTA0IFx1YmQ4MFx1ZDEzMCBIXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjYTlcdWM3OTBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWUwMFx1Yzc5MFx1YWMwMCBXXHVhYzFjXHVjNTI5IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgTFx1Yzc3OCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVhZTAwXHVjNzkwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViMmU4XHVjNWI0XHViOTdjIFx1Yzc3ZFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0MCAxMDxzdXA+MTg8XC9zdXA+XHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjQxOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkxldHRlciBHcmlkIiwiZGVzY3JpcHRpb24iOiI8cD5Db25zaWRlciB0aGUgZm9sbG93aW5nIGxldHRlciBncmlkOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA1XC9TY3JlZW4gc2hvdCAyMDExLTA1LTEwIGF0IDEyXzE0XzAzIEFNLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjgxcHg7IHdpZHRoOjEzN3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSA3IHdheXMgdG8gcmVhZCB0aGUgd29yZCBUQVJUVSBmcm9tIHRoZSBncmlkOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA1XC9TY3JlZW4gc2hvdCAyMDExLTA1LTEwIGF0IDEyXzE0XzQ2IEFNLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE0NHB4OyB3aWR0aDo1ODhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIGxldHRlciBncmlkIGFuZCBhIHdvcmQsIHlvdXIgdGFzayBpcyB0byBkZXRlcm1pbmUgdGhlIG51bWJlciBvZiB3YXlzIHRoZSB3b3JkIGNhbiBiZSByZWFkIGZyb20gdGhlIGdyaWQuIFRoZSBcdWZiMDFyc3QgbGV0dGVyIG9mIHRoZSB3b3JkIGNhbiBiZSBpbiBhbnkgY2VsbCBvZiB0aGUgZ3JpZCwgYW5kIGFmdGVyIGVhY2ggbGV0dGVyLCB0aGUgbmV4dCBsZXR0ZXIgaGFzIHRvIGJlIGluIG9uZSBvZiB0aGUgbmVpZ2hib3VyIGNlbGxzIChob3Jpem9udGFsbHksIHZlcnRpY2FsbHkgb3IgZGlhZ29uYWxseSkuIEEgY2VsbCBjYW4gYmUgdXNlZCBtdWx0aXBsZSB0aW1lcyB3aGVuIHJlYWRpbmcgdGhlIHdvcmQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIFx1ZmIwMWxlIGdyaWQuaW4gY29udGFpbnMgdGhyZWUgaW50ZWdlcnM6IEggKDEgJmxlOyBIICZsZTsgMjAwKSwgdGhlIGhlaWdodCBvZiB0aGUgZ3JpZCwgVyAoMSAmbGU7IFcgJmxlOyAyMDApLCB0aGUgd2lkdGggb2YgdGhlIGdyaWQsIGFuZCBMICgxICZsZTsgTCAmbGU7IDEwMCksIHRoZSBsZW5ndGggb2YgdGhlIHdvcmQuIFRoZSBmb2xsb3dpbmcgSCBsaW5lcyBlYWNoIGNvbnRhaW5pbmcgVyBsZXR0ZXJzIGRlc2NyaWJlIHRoZSBncmlkLiBUaGUgbGFzdCBsaW5lIGNvbnRhaW5pbmcgTCBsZXR0ZXJzIGRlc2NyaWJlcyB0aGUgd29yZC4gQWxsIGxldHRlcnMgaW4gdGhlIGdyaWQgYW5kIGluIHRoZSB3b3JkIGFyZSB1cHBlcmNhc2UgRW5nbGlzaCBsZXR0ZXJzIChBLiAuIC4gWikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiB0aGUgXHVmYjAxbGUgZ3JpZC5vdXQgc2hvdWxkIGNvbnRhaW4gb25lIGludGVnZXI6IHRoZSBudW1iZXIgb2Ygd2F5cyB0aGUgd29yZCBjYW4gYmUgcmVhZCBmcm9tIHRoZSBncmlkLiBZb3UgbWF5IGFzc3VtZSB0aGF0IHRoZSBhbnN3ZXIgaXMgYWx3YXlzIGF0IG1vc3QgMTA8c3VwPjE4PFwvc3VwPi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2010 P1번