DIRECTIONS = [
        (1, 0),
        (-1, 0),
        (0, 1),
        (0, -1)
        ]

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board:
            return False

        # first point
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0] and self.dfs(board, word[1:], i, j, {(i,j)}):
                    return True
        return False # after all search

    def dfs(self, board, word, i, j, visited):
        # end of recursion
        if not word:
            return True

        # define and split
        for (dx, dy) in DIRECTIONS:
            next_x, next_y = i+dx, j+dy
            # print(next_point)
            if self.is_valid_point(next_x, next_y, board, visited, word[0]):
                visited.add((next_x, next_y))
                if self.dfs(board, word[1:], next_x, next_y, visited):
                    return True
                visited.remove((next_x, next_y)) # backtracking

        return False

#     def dfs(self, board, word, start_point, visited):
#         # end of recursion
#         if not word:
#             return True

#         # define and split
#         for (dx, dy) in DIRECTIONS:
#             next_point = (start_point[0]+dx, start_point[1]+dy)
#             # print(next_point)
#             if self.is_valid_point(next_point, board, visited, word[0]):
#                 visited.add(next_point)
#                 if self.dfs(board, word[1:], next_point, visited):
#                     return True
#                 visited.remove(next_point) # backtracking

#         return False

    def is_valid_point(self, x, y, board, visited, word):
        if (x, y) in visited:
            return False
        r = len(board)
        c = len(board[0])
        return 0 <= x < r and 0 <= y < c and board[x][y] == word