Problem J5: CCC Word Hunt

Problem DescriptionCopy Anchor Link

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.

Input SpecificationCopy Anchor Link

The first line of input will contain a string of distinct uppercase letters, $W$, representing the word you are to search for in the grid. The length of $W$ will be at least two. The second line of input will be an integer $R~(1 \le R \le 100)$, where $R$ is the number of rows in the grid. The third line of input will be an integer $C~(1 \le C \le 100)$, where $C$ is the number of columns in the grid.

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

The following table shows how the available 15 marks are distributed:

Output SpecificationCopy Anchor Link

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

Sample Input 1Copy Anchor Link

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

Output for Sample Input 1Copy Anchor Link

3

Explanation of Output for Sample Input 1Copy Anchor Link

The word MENU is hidden three times in the grid. Once horizontally, once vertically, and once diagonally as shown. Notice that a single letter can be used more than once.

Sample Input 2Copy Anchor Link

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

Output for Sample Input 2Copy Anchor Link

4

Explanation of Output for Sample Input 2Copy Anchor Link

The word NATURE is hidden four times in the grid. Once diagonally, once vertically, and twice on perpendicular line segments.