# Given an m x n grid of characters board and a string word, return true if word exists in the grid.
# 
# The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
# 
#  
# 
# Example 1:
# 
# 
# Input: board = [
#   ["A","B","C","E"],
#   ["S","F","C","S"],
#   ["A","D","E","E"]
# ], word = "ABCCED"
# Output: true

def main(board, word):
    ROWS = len(board)
    COLS = len(board[0])

    pos = 0

    directions = [
        (0, 1),
        (1, 0),
        (0, -1),
        (-1, 0),
    ]
    def dfs(row, col, pos):
        # import pdb; pdb.set_trace()
        if pos == len(word):
            return True

        if (row < 0 or row >= ROWS) or (col < 0 or col >= COLS) or board[row][col] == "#":
            return False

        letter = board[row][col]
        if letter == word[pos]:
            pos += 1
            board[row][col] = "#"
            for direction in directions:
                if dfs(row + direction[0], col + direction[1], pos):
                    return True
            board[row][col] = letter

    for r in range(ROWS):
        for c in range(COLS):
            if dfs(r, c, 0):
                return True
    return False


board = [["b"],["a"],["b"],["b"],["a"]]
word = "baa"

print(main(board, word))