Word Search

Given a grid of letters and a word, print true if the word can be formed by a path of adjacent cells (horizontally or vertically), using each cell at most once.

Example

Input grid 3x4, word ABCCED Output: true

Approach

Try every cell as a possible starting point. From there, DFS: if the current cell matches the current letter of the word, mark it visited, recurse into all 4 neighbors for the next letter, then un-mark it before returning (backtrack) — the un-marking is what allows the same cell to be reused by a different search path starting elsewhere.

Input format

Line 1: number of rows R Next R lines: space-separated grid row (letters) Last line: the word to search for

Print true or false.