class Solution:
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if word=="":
            return True
        m=len(board)
        if m==0:
            return False
        n=len(board[0])
        isvisited=[[0 for i in range(n)]for j in range(m)]
        def dfs(board,isvisited,word,m,n,i,j):
            if word=="":
                return True
            if i<0 or i>=m or j<0 or j>=n or word[0]!=board[i][j] or isvisited[i][j]==1:
                return False
            else:
                isvisited[i][j]=1
                res=dfs(board,isvisited,word[1:],m,n,i+1,j) or dfs(board,isvisited,word[1:],m,n,i-1,j)or dfs(board,isvisited,word[1:],m,n,i,j-1) or dfs(board,isvisited,word[1:],m,n,i,j+1)
                isvisited[i][j]=0
            return res
        for i in range(m):
            for j in range(n):
                if dfs(board,isvisited,word,m,n,i,j):
                    return True
        return False

solution=Solution()
board =[  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']]
word = "ABCCED"
print(solution.exist(board,word))
