Word Search

A grid of letters is given. A word exists in the grid if it can be spelled by moving from cell to cell up, down, left or right, without using any cell twice in the same word. Answer this for several words.

Input:

• line 1: r c
• next r lines: c letters each
• next line: q
• next q lines: one word each

Output: for every word, true or false on its own line.

Constraints: 1 ≤ r, c ≤ 6, 1 ≤ q ≤ 50, 1 ≤ word length ≤ 15; letters are upper- and lowercase English letters.

Think about it: DFS from every cell with backtracking: mark the cell as used, explore the 4 neighbours for the next letter, then unmark it on the way back.