# 给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

# 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。

# 同一个单元格内的字母在一个单词中不允许被重复使用。

# 示例:

# 输入:

# words = ["oath","pea","eat","rain"] and board =

# [

#  ['o','a','a','n'],

#  ['e','t','a','e'],

#  ['i','h','k','r'],

#  ['i','f','l','v']

# ]

# 输出: ["eat","oath"]

# 说明:

# 你可以假设所有输入都由小写字母 a-z 组成。

# 提示:

#    你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？

#    如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？

#    前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。

import random

words = ["oath", "pea", "eat", "rain"]

board = [

    ['o', 'a', 'a', 'n'],

    ['e', 't', 'a', 'e'],

    ['i', 'h', 'k', 'r'],

    ['i', 'f', 'l', 'v']

]

# 判断附近有单词能够和之前的组成同一个单词不

def is_same_word(x, y, word, i):

    if i >=len(word):

        return True

    # x,y是当前单词在board的坐标,只要有一个相同就递归进去

    if x + 1 < board.__len__() and y < board.__len__():

        if board[x + 1][ y] == word[i]:

            return  is_same_word(x + 1, y, word, i + 1)

    if y+1<board.__len__() and x<board.__len__():

        if board[x][y + 1] == word[i]:

            return  is_same_word(x, y + 1, word, i + 1)

    if x - 1 < board.__len__() and y < board.__len__():

        if board[x - 1][ y] == word[i]:

            return  is_same_word(x - 1, y, word, i + 1)

    if x < board.__len__() and y - 1 < board.__len__():

        if board[x][ y - 1] == word[i]:

            return  is_same_word(x, y - 1, word, i + 1)

    return False

#满足条件的word的集合

words_ok = []

# 遍历找到words中的每个单词

for word in words:

    # 然后在Board中遍历 与word首字母相同的

    for board_x,board_x_item in enumerate(board):

        for board_y,board_y_item in enumerate(board_x_item):

            if board[board_x][board_y] == word[0]:

                if is_same_word(board_x,board_y,word,1):

                    words_ok.append(word)

print(words_ok)