def get_moves(pos,board):
    rows = len(board)
    cols = len(board[0])
    i,j = pos
    moves = []
    if j-1>=0:
        left = (i,j-1)
        moves.append(left)
    if i-1>=0:
        up = (i-1,j)
        moves.append(up)
    if i+1<(rows):
        down = (i+1,j)
        moves.append(down)
    if j+1<(cols):
        right = (i,j+1)
        moves.append(right)
    if i-1>=0 and j-1>=0:
        top_left = (i-1,j-1)
        moves.append(top_left)
    if i+1<rows and j-1>=0:
        down_left = (i+1,j-1)
        moves.append(down_left)
    if i-1>=0 and j+1<cols:
        top_right = (i-1,j+1)
        moves.append(top_right)
    if i+1<rows and j+1<(cols):
        down_right = (i+1,j+1)
        moves.append(down_right)
    return moves





def dfs(word,board):
    start = 0
    stack = []
    rows = len(board)
    cols = len(board[0])
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == word[start]:
                s = set()
                s.add((i,j))
                stack.append(((i,j),s,1))
    while stack:
        (i,j), visited,count = stack.pop()
        print(i,j,count,word[count-1])
        if count == len(word):
            return True
        moves = get_moves((i,j),board)
        for (new_i,new_j) in moves:
            print(new_i,new_j)
            if (new_i,new_j) not in visited and board[new_i][new_j] == word[count]:
                visited.add((new_i,new_j))
                stack.append(((new_i,new_j),set(visited),count+1))
                visited.remove((new_i,new_j))
    return False




def wordBoggle(board, words):
    rows = len(board)
    cols = len(board[0])
    ans = []
    words.sort()
    for word in words:
        if dfs(word,board):
            ans.append(word)

    return ans