1186. Where Can the Word Start

A grid of r rows and c columns holds uppercase letters. A word can be READ from a cell if its letters appear along a walk that starts there, steps only between cells sharing an edge, and uses no cell twice within that one reading.

Problem #1150 asks whether the word is present anywhere and answers YES or NO. This asks a sharper question: print every cell the word can start from.

3 4 the word ABCCED can be read starting ABCE from cell 1 only SFCS -> 1 ADEE ABCCED

## What most people try first

Find one reading, report its starting cell, and stop. That answers #1150, not this. Several cells can start the same word, and the search has to be run again from each of them, because a reading that fails from one cell says nothing about another.

The second attempt is worse: run the search once with a single shared visited grid across all starting cells. A cell used by a failed attempt from cell 1 is then unavailable to the attempt from cell 7, so cells drop out of the answer for no reason. The visited grid belongs to one reading, not to the whole run.

## Naming the cells

The answer is a set of cells, so the cells need names. Number them 1 to r * c, left to right along row 1, then row 2, and so on. The cell in row i and column j, counting from 1, is therefore (i - 1) * c + j. Print the numbers in INCREASING order, separated by single spaces, on a single line. That is a canonical order, so there is nothing to decide and nothing to get wrong. If the word can start nowhere, print none.

## The method

For each cell in turn, ask whether a reading starting there exists:

canRead(i, j, k): # k letters already matched if k == length(word): return true 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 if canRead(ni, nj, k + 1): return true seen[ni][nj] = false return false

## The mark that has to be released

A cell must be marked on the way in and UNMARKED on the way out. Marking and never releasing is the characteristic bug of this whole topic: it finds some routes and silently misses others, because a dead end leaves cells marked that a later route needed. Problem #1150 states that rule; here it is measurable, because a missing unmark changes the number of lines you print rather than one yes or no.

The return true on success is correct here and is worth separating from the unmark. Once one reading is found the cell is in the answer and nothing more needs exploring from it, so leaving marks behind on the way out is harmless. That shortcut is only available because the question is existence. Problem #1187 counts the readings instead, and there the search must unwind fully.

## Why it is correct

seen holds exactly the cells of the reading under construction, by the same mark-and-release argument as #1185. A neighbour is therefore offered precisely when it continues the reading legally, so canRead returns true exactly when a legal reading exists. Running it from every cell independently, with a fresh seen, answers the question for every cell.

## The settled boundaries

A one-letter word can be read from any cell holding that letter, with no steps at all. A one-by-one grid can start only a one-letter word. If no cell works, the output is none.

## Cost

At most 4^(L-1) walks from each of r * c cells, where L is the word length, cut down sharply in practice because a letter has to match at every step. 36 cells and a length of 8 at the stated limits.

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