시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (하단 참고) 512 MB 38 20 17 51.515%

문제

N×M 크기의 표의 각 칸에 알파벳 대문자가 하나씩 쓰여 있다. 단어 S가 주어졌을 때, 표에 단어 S가 있는지 없는지 구하는 프로그램을 작성하시오.

단어 S가 표에 존재하려면, 표의 한 칸에서 시작해, 연속해서 그 단어의 모든 알파벳이 순서대로 등장해야 한다. 이때, 연속하는 방향은 위, 아래, 오른쪽, 왼쪽, 대각선 방향 모두 가능하다. 대각선 방향은 왼쪽 위, 오른쪽 아래, 오른쪽 위, 왼쪽 아래 방향이 모두 가능하다. 연속하는 방향이 중간에 바뀌면 안 된다.

입력

첫째 줄에 길이가 100보다 작거나 같은 단어 S가 주어진다. S는 알파벳 대문자로만 이루어져 있다.

둘째 줄에는 표의 행의 개수 N과 열의 개수 M이 주어진다. NM은 100보다 작거나 같은 자연수이다.

셋째 줄부터 N개의 줄에는 표의 각 행에 들어있는 알파벳이 주어진다.

출력

입력으로 주어진 표에 단어 S가 존재하면 1을, 없으면 0을 출력한다.

예제 입력 1

ABCD
5 5
ACDBE
ABCED
ACCEE
ACHDF
ACBCE

예제 출력 1

1

예제 입력 2

STR
6 6
STARTS
STRSTR
RRTSRE
SRSTRR
STRTSR
STSTSS

예제 출력 2

1

예제 입력 3

AFAFK
2 2
AB
CD

예제 출력 3

0

예제 입력 4

AAAB
4 4
AAAA
ABBA
ABBA
AAAA

예제 출력 4

0

힌트

예제 1의 경우에 ABCD는 아래와 같이 등장한다.

ACDBE
ABCED
ACCEE
ACHDF
ACBCE

예제 2의 경우에 STR은 등장한다. STR은 매우 많이 등장하는데, 일부를 아래에 굵게 표시했다.

STARTS
STRSTR
RRTSRE
SRSTRR
STRTSR
STSTSS

출처

  • 문제의 오타를 찾은 사람: jh05013

시간 제한 안내

아래 적혀있지 않은 시간 제한은 언어 도움말에 적혀있는 기준을 따른다.

  • Python 3: 12초
  • PyPy3: 12초
  • Python 2: 12초
  • PyPy2: 12초

채점

  • 예제는 채점하지 않는다.