9094: CCC '23 J5 - CCC Word Hunt
[Creator : ]
Description
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.
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
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≤R≤100)$, where $R$ is the number of rows in the grid.
The third line of input will be an integer $W\ (1≤W≤100)$, where $W$ 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:
The second line of input will be an integer $R\ (1≤R≤100)$, where $R$ is the number of rows in the grid.
The third line of input will be an integer $W\ (1≤W≤100)$, where $W$ 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:
| Marks | Word Placement |
|
$2$ |
On one horizontal line segment |
|
$2$ |
On one horizontal or vertical line segment |
|
$2$ |
On one horizontal, vertical, or diagonal line segment |
|
$9$ |
On one line segment or two perpendicular line segments |
Output
The output will consist of a single non-negative integer $H$, representing the number of times the word is hidden in the grid.
Sample 1 Input
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
Sample 1 Output
3
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 2 Input
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
Sample 2 Output
4
