1286 - 单词搜索

通过次数

14

提交次数

29

Time Limit : 1 秒
Memory Limit : 128 MB

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,输出 true ;否则,输出 false

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

Input

第一行为2个整数m,n,分别是board的行数和列数

以下m行每行n个字符,表示board的元素

第m+2行为一个字符串word

Output

word 是否存在于网格中,存在则输出true,否则输出false

Examples

Input

3 4
ABCE
SFCS
ADEE
ABCCED

Output

true

Input

3 4
ABCE
SFCS
ADEE
SEE

Output

true

Input

3 4
ABCE
SFCS
ADEE
ABCB

Output

false

Hint

  • m == board.length

  • n = board[i].length

  • 1 <= m, n <= 6

  • 1 <= word.length <= 15

  • boardword 仅由大小写英文字母组成