964. Every Listed Word Hidden in the Grid

A grid of r rows by c columns of lowercase letters is given, then n listed words. A word is PRESENT when its letters can be read off a path through the grid that starts anywhere, steps only between cells sharing an edge (up, down, left or right), and never uses the same cell twice within that word.

Print the present words in alphabetical order, one per line, or none if there are none.

``` grid words found o a a n e t a e oath, pea, eat, rain eat i h k r oath i f l v

grid words found a b abdc, acdb, abcd abdc c d acdb ```

In the second grid, abcd needs a step from b to c, which are diagonal neighbours and not allowed. abdc reads a, b, d, c going right, down, left.

## The obvious program, and what it repeats

Search the grid once per word. Each search starts at up to r * c cells and branches four ways at the first step and three thereafter, so a word of length 10 explores up to 4 * 3^8 paths from one start. With 100 words and 100 starting cells that is roughly 100 * 100 * 26244, about 2.6 * 10^8 path steps, and almost all of them are spent re-walking prefixes the words share: cat, cart and car each pay for the c and the a separately.

## Search the grid once, with the words as the map

Put all the words in one trie. Then run a single depth first walk over the grid in which the trie node moves in step with the path.

``` dfs(i, j, node): nxt = child[node][grid[i][j]] if nxt does not exist: return # no listed word continues this way if a word ends at nxt: record that word mark (i, j) as used for each edge neighbour (ni, nj) not used: dfs(ni, nj, nxt) unmark (i, j)

for every cell (i, j): dfs(i, j, root) ```

The trie is the pruning. A path whose letters are not a prefix of any listed word is abandoned on the character that makes it so, not after ten letters, and the shared prefixes of the words are walked once between them rather than once each.

## Why the mark has to be undone

The "no cell twice" rule applies WITHIN one path, not across the whole search. So the cell is marked before descending and unmarked after returning, which is the standard backtracking discipline. Leaving it marked makes later paths think the cell is unavailable and silently loses answers, and marking it after the recursion instead of before lets a path step back onto itself.

## Why finding a word does not end its branch

A word ending at a node does not mean the walk should stop there: a longer listed word may continue through the same cells. With aa and aaa both listed, the walk records aa and keeps going to find aaa. Recording and continuing are independent decisions.

## Duplicates

The same word can be found by several different paths. The answer is a SET of words, so record it once; collecting into a set, or a found flag per word, is what makes the output right. Printing every discovery gives the same word several times.

## Cost

Building is O(total length of the words), at most 1 + 100 * 10 = 1001 nodes. The grid search is bounded by the paths that stay inside the trie, which for these limits is well under the unpruned figure above. Nothing here overflows.

## Against problem 951

951 walks the trie alone and prunes on the word ends. This walks the trie and the GRID together, with the grid deciding which letters are available and the trie deciding which are worth taking.

Constraints - `1 ≤ r ≤ 10`, `1 ≤ c ≤ 10` - `1 ≤ n ≤ 100` - Every listed word is 1 to 10 lowercase English letters. - The listed words are pairwise different.