Hidden Words
InterviewTime limit2sMemory limit512 MB
Given a grid of up to 10x10 letters and up to 100,000 query words of length at most 10, count how many words can be traced through adjacent, non-repeating cells.
- Level
Medium7 of 10
- Topics
- Backtracking, DFS, Trie, Brute force
- Solved
- No attempts yet
Problem
Ingrid is solving the Saturday newspaper Hidden Words in a Grid puzzle, but is finding it a bit tedious to do by hand. Luckily Ingrid knows how to program, and has written a neat image recognition routine that converts a picture of the puzzle into a nice text-based format. However, she is struggling with writing the program that actually solves the puzzle. Can you help her out?
A word is contained within an h by w grid if the word can be constructed by starting in a cell in the grid and walking from there to neighboring unvisited cells. A cell neighbors another cell if it is adjacent, not including diagonal movement. Given such a grid and a list of words, determine how many of the words in the list are contained in the grid.
Input
The first line consists of two integers h and w (1 ≤ h, w ≤ 10), the height and width of the grid. Then h lines follow, each containing a string of length w consisting exclusively of uppercase letters describing one row of the grid. Then follows a line with a single integer n (1 ≤ n ≤ 100 000), indicating the number of words Ingrid is looking for. Finally the n words follow, each on a separate line. None of these words are longer than 10 characters.
Output
The output consists of a single number, the number of words underneath the grid that are contained in the grid.