아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

CCC Word Hunt

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

요약
단어가 격자에서 일직선으로, 또는 한 글자에서 직각으로 꺾이는 두 선분으로 나타나는 횟수를 센다.
난이도

보통10점 중 4점

유형
DFS, 백트래킹, 행렬, 구현
정답자
아직 제출이 없습니다

문제

In the CCC Word Hunt, words are hidden in a grid of letters. The letters of a hidden word always appear in order on horizontal, vertical, or diagonal line segments in one of two ways. One way is for the letters of a word to appear on one line segment. The other way is for the letters of a word to appear on one line segment up to some letter and then on a second line segment that forms a right angle at this letter.

Given a grid of letters and a single word to search for, your job is to determine the number of times that particular word is hidden in the grid.

입력

The first line of input will contain a string of distinct uppercase letters, WW, representing the word you are to search for in the grid. The length of WW will be at least two.

The second line of input will be an integer RR (1≤R≤100)(1 \le R \le 100), where RR is the number of rows in the grid.

The third line of input will be an integer CC (1≤C≤100)(1 \le C \le 100), where CC is the number of columns in the grid.

The remaining input will provide the letters in the grid. It will consist of RR lines, where each line contains CC uppercase letters separated by single spaces.

출력

The output will consist of a single non-negative integer HH, representing the number of times the word is hidden in the grid.

예제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