class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def isvalid(i,j):
            return 0<=i<R and 0<=j<C
        def helper(i,j,idx):
            #print(i,j)
            if idx == len(word):
                return True
            for di, dj in [[-1,0],[0,1],[1,0],[0,-1]]:
                if isvalid(i+di,j+dj) and not visited[i+di][j+dj] and board[i+di][j+dj] == word[idx]:
                    visited[i][j]=1
                    if helper(i+di,j+dj,idx+1):
                        return True
                    visited[i][j]=0

        self.flag = False
        R = len(board)
        C= len(board[0])
        visited = [[0]*C for _ in range(R)]
        start = []
        for i in range(R):
            for j in range(C):
                if board[i][j] == word[0]:
                    start.append((i,j))

        for i,j in start:
            visited[i][j]=1
            if helper(i,j,1):
                return True
            visited[i][j]=0