def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = set()

    def dfs(r, c, k):
        if k == len(word):
            return True
        if (
            r < 0
            or r >= rows
            or c < 0
            or c >= cols
            or (r, c) in visited
            or board[r][c] != word[k]
        ):
            return False
        visited.add((r, c))
        ok = (
            dfs(r + 1, c, k + 1)
            or dfs(r - 1, c, k + 1)
            or dfs(r, c + 1, k + 1)
            or dfs(r, c - 1, k + 1)
        )
        visited.remove((r, c))
        return ok

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False


if __name__ == "__main__":
    board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
    print(exist(board, "ABCCED"))
    print(exist(board, "SEE"))
    print(exist(board, "ABCB"))