1187. How Many Ways Does the Word Read

Same grid and same rules as problem #1186: uppercase letters, steps between cells sharing an edge, no cell used twice within one reading. Print how many distinct readings of the word exist in the whole grid.

Two readings are distinct when they use a different sequence of cells, so the same cells walked in a different order count separately, and a reading starting from a different cell counts separately too.

2 2 the word AA reads eight ways AA -> 8 AA

Count that by hand, because it is the shape of every answer here. A reading of AA is an ordered pair of neighbouring cells. The 2 by 2 grid has four pairs of cells sharing an edge, and each pair can be read in either direction, so there are eight readings. Notice that the answer already exceeds the four cells of the grid, which is why counting the cells #1186 reports is a different question.

## What most people try first

Reuse #1186 and count the cells it reports. That answers a different question. #1186 asks from how many cells the word CAN be read, which is at most r * c. This asks how many readings there are in total, which is unbounded by the grid size and is much larger whenever the letters repeat.

The second mistake is subtler and it is the real lesson. #1186 is allowed to return true the moment it finds a reading, and leaving visited marks behind on the way out is harmless there because nothing more will be searched from that cell. Counting removes that licence. The search has to visit every reading, so every mark must be released on every path out, not only on the failing ones.

## The method

count(i, j, k): # k letters matched, (i, j) is the k-th if k == length(word): return 1 total = 0 for each of the four neighbours (ni, nj): if inside and not seen[ni][nj] and grid[ni][nj] == word[k]: seen[ni][nj] = true total += count(ni, nj, k + 1) seen[ni][nj] = false # always, not only on failure return total

and the answer is the sum over every starting cell whose letter matches the first letter of the word.

## Why it is correct

The recursion counts readings by their first differing step, which partitions them: two readings that agree on the first k cells and differ at step k + 1 are counted in different branches, and no reading is counted in two branches. The base case contributes exactly one for each completed reading. So the total is the number of readings, with no double counting and nothing missed.

The mark-and-release argument is the same as #1185, with the stronger requirement that the release happens unconditionally, because the search continues after a success rather than returning.

## The settled boundaries

A one-letter word is read once from each cell holding that letter, so the answer is simply how many such cells there are. A word whose first letter appears nowhere gives 0, which is printed as 0 and not as none, because the answer here is a number rather than a list.

## Overflow

At the stated limits the count cannot be large. The grid holds at most 25 cells and a reading uses at most 10 of them, so the count is bounded by the number of walks of length 9 in a 25 cell grid, far inside the 2147483647 a signed 32 bit integer holds. No wide type is needed, and claiming otherwise would be a false warning. Problem #1190 is where this topic genuinely overflows.

## Cost

At most 4^(L-1) walks from each cell, with a letter match required at every step, which in practice cuts the tree hard unless the grid is nearly uniform. The all-same-letter grids in the tests are the worst case on purpose.

Constraints - `1 ≤ r, c ≤ 5` - `1 ≤ length of the word ≤ 10` - The grid and the word hold uppercase English letters only.