BacktrackingMatrixDFS
A grid of letters is given. Decide whether a word can be traced in it by moving to horizontally or vertically adjacent cells, using each cell at most once in the path.
Input
Line 1: r and c. Next r lines: each a row of c lowercase letters (no spaces). Last line: the word.
Output
Print true if the word exists in the grid, otherwise false.
Constraints
1 <= r, c <= 6 1 <= length of word <= 12
Example 1
Input
3 4 abce sfcs adee abcced
Output
true
The word can be traced a-b-c-c-e-d without reusing a cell.
Example 2
Input
3 4 abce sfcs adee abcb
Output
false
The second b would need the same cell twice.