시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 633 | 176 | 144 | 32.952% |
유니콘은 체스에서 나이트와 비슷한 말이다. 단, 나이트는 두 칸을 한 방향으로 움직이고, 또 다른 한 칸을 다른 방향으로 움직이지만, 유니콘은 두 칸보다 많은 칸을 한 방향으로 움직이고, 한 칸보다 많은 칸을 또다른 방향으로 움직인다.
좀 더 정확하게 유니콘이 움직이는 방법을 살펴보면 다음과 같다.
체스판의 크기는 N*M이다. 체스판의 각 칸에는 알파벳의 처음 L개의 문자 중 하나가 쓰여 있다.
N, M, L, 그리고 단어가 주어진다. 유니콘이 움직인 경로 (유니콘을 놓은 곳)가 입력으로 주어진 단어와 일치하는 경우의 수를 출력하는 프로그램을 작성하시오.
첫째 줄에 N, M, L이 주어진다. N과 M은 300보다 작거나 같은 자연수이다. L은 26보다 작거나 같은 자연수이다. 둘째 줄에 단어가 주어진다. 단어의 길이는 최대 50이며, 알파벳 대문자로만 이루어져 있다. 셋째 줄 부터 N개의 줄에 체스판에 쓰여 있는 단어가 주어진다.
첫째 줄에 경로를 1,000,000,007로 나눈 나머지를 출력한다.
3 4 2 AB ABBA AAAA BBBB
2
5 5 2 CD ABBAA AAABB BBBBB ABABA ABBBB
0
4 4 1 AA AAAA AAAA AAAA AAAA
20
4 4 1 AAAAA AAAA AAAA AAAA AAAA
172
1 1 5 ABCDE C
0
8 8 26 TOPCODER AILFPSPF DZIOMYCE QOODZARU YVOTLTRX LSRIGANL LCIUUSNF IWVXKTDE OVPPNXRD
1
20 20 2 AAAAA ABBAAAAABBBBBBBABABA ABBBBBABAAAABBAAABAA BAAABAABAABBABABBABB BBABBAAAABABAAAAABBA BBABAABABBAABABABBBA BABABAABABBBABBAABBA BAABBAAABBBABBABAAAA BAABBBBABAABAAAAABAA AABABAAAAABBBABABBBA BBAABAAABBAABAAAAABA BAAAAABABBAAABABABBA ABBAABBBABABBABAAABB AAAABAAAAAAAABBBAABB AAABABAAAAAABAAABABB AAABABABBABABAAABBBA AAABBBBAABBAABAAABBA BBBBAAABBABABAAAABAB BBAABBAABAAAABAABABA BBBAABBABABBBBBBBBBA AAABABBBBAABABBBBBBB
373977054