Word Grid
Time limit1sMemory limit128 MB
Count the number of paths in an HxW grid moving to 8-directional neighbors (cells reusable) that spell out a given word of length L.
- Level
Medium4 of 10
- Topics
- Dynamic programming, Matrix, Implementation
- Solved
- No attempts yet
Problem
You are given an H by W grid filled with uppercase English letters and a word of length L.
The first letter of the word may start at any cell in the grid. For each letter after that, you must move from the previous cell to an adjacent cell. Adjacent cells are the 8 cells in the vertical, horizontal, and diagonal directions. The same cell may be used more than once.
Count the number of distinct ways to read the given word.
Input
The first line contains three integers H, W, and L. H is the height of the grid, W is the width of the grid, and L is the length of the word. (1 <= H, W <= 200, 1 <= L <= 100)
The next H lines each contain a string of length W describing one row of the grid. The last line contains the word of length L. Every character is an uppercase English letter.
Output
Output the number of distinct ways to read the given word. The answer does not exceed 10^18.