题目描述

给定一个 $m \times n$ 二维字符网格 $board$ 和一个单词（字符串）列表 $words$， 返回所有二维网格上的单词 。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

输入格式

第一行两个整数 $n$ $m$,表示二维网络的列与行。 接下来 $m$ 行，每行 $n$ 个字符。

接下来第 $m + 2$ 行，一个整数 $\text{k}$，表示单词（字符串）列表 $words$ 中共有 $k$ 个单词；接下来 $k$ 行， 每行一个单词（字符串）。

输出格式

按字典序输出列表 $words$中在二维网格上的单词，每行一个。如果一个也没有就输出 -1 。

样例

样例 1：

4 4
oaan
etae
ihkr
iflv
4
oath
pea
eat
rain

eat
oath

样例 2：

2 2
ab
cd
1
abcd

-1

数据规模

• $m == board.length$
• $n == board[i].length$
• $1 <= m, n <= 12$
• $board[i][j]$ 是一个小写英文字母
• $1 <= words.length <= 3 * 10^4$
• $1 <= words[i].length <= 10$
• $words[i]$ 由小写英文字母组成
• $words$ 中的所有字符串互不相同

SOURCE

leetcode 212