시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 357 | 83 | 68 | 30.909% |
유니콘은 체스에서 나이트와 비슷한 말이다. 단, 나이트는 두 칸을 한 방향으로 움직이고, 또 다른 한 칸을 다른 방향으로 움직이지만, 유니콘은 두 칸보다 많은 칸을 한 방향으로 움직이고, 한 칸보다 많은 칸을 또다른 방향으로 움직인다.
좀 더 정확하게 유니콘이 움직이는 방법을 살펴보면 다음과 같다.
체스판의 크기는 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