1150. Is the Word in the Grid
A grid of r rows and c columns holds uppercase letters. A word is present
if its letters can be read by stepping between cells that share an edge, using
each cell at most once within a single reading.
Print YES if the word is present, otherwise NO.
Steps are up, down, left and right only, never diagonal. A cell may be reused by a DIFFERENT reading but never twice within one, which is exactly what makes this backtracking rather than a plain traversal: a cell must be released when the search leaves it, so another route can use it.
Marking a cell visited and never releasing it is the characteristic bug. It finds some words and silently misses others, because a dead end poisons cells a later route needed.
Constraints - `1 ≤ r, c ≤ 6` - `1 ≤ length of the word ≤ 12` - The grid and the word contain uppercase English letters only.
Input
The first line contains two integers r and c.
The next r lines each contain c uppercase letters with no spaces.
The last line contains the word to search for.
Output
Print YES if the word can be read in the grid, otherwise NO.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.