만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

CCC 단어 찾기

면접 대비

시간 제한1초메모리 제한1024 MB

요약
글자 격자에서 단어가 한 직선 또는 직각으로 만나는 두 직선을 따라 숨겨진 경우의 수를 셉니다.
난이도

보통10점 중 4점

유형
완전 탐색, 행렬, 구현
정답자
아직 제출이 없습니다

문제

CCC 단어 찾기에서는 단어가 문자 격자에 숨겨져 있다. 숨겨진 단어의 문자들은 항상 수평, 수직, 대각선 선분 위에 순서대로 놓여 있다. 단어가 숨겨지는 방식은 두 가지이다. 첫 번째는 단어의 모든 문자가 하나의 선분 위에 놓이는 경우이다. 두 번째는 단어의 문자가 어느 문자까지는 한 선분 위에 있고, 그 문자에서 직각을 이루는 두 번째 선분 위로 이어지는 경우이다.

문자 격자와 찾을 단어 하나가 주어졌을 때, 그 단어가 격자에 숨겨져 있는 횟수를 구하라.

입력

첫 번째 줄에는 찾을 단어 WW가 주어진다. WW는 서로 다른 대문자로 이루어진 문자열이며, 길이는 2 이상이다.

두 번째 줄에는 행의 수 RR (1≤R≤100)(1 \le R \le 100)이 주어진다.

세 번째 줄에는 열의 수 CC (1≤C≤100)(1 \le C \le 100)이 주어진다.

나머지 RR개의 줄에는 각각 공백으로 구분된 대문자 CC개가 있다.

출력

음이 아닌 정수 HH를 하나 출력한다. HH는 단어가 격자에 숨겨져 있는 횟수이다.

예제2

  1. 예제 1

    입력
    MENU
5
7
F T R U B L K
P M N A X C U
A E R C N E O
M N E U A R M
M U N E M N S
    예상 출력
    3

  2. 예제 2

    입력
    NATURE
6
9
N A T S F E G Q N
S A I B M R H F A
C F T J C U C L T
K B H U P T A N U
D P R R R J D I R
I E E K M E G B E
    예상 출력
    4