class Solution:
    """
    @param board: A list of lists of character
    @param word: A string
    @return: A boolean
    """
    def exist(self, board, word):
        # write your code here
        self.m,self.n=len(board),len(board[0])
        self.visited=[[0]*self.n for _ in range(self.m)]
        self.direction=[[0,1],[1,0],[0,-1],[-1,0]]

        #find out starting point:
        for i in range(self.m):
            for j in range(self.n):
                if board[i][j]==word[0] and self.findPath(i,j,board,word,1):
                    return True
                self.visited=[[0]*self.n for _ in range(self.m)]
        return False

    def findPath(self,i,j,board,word,index):
        if index==len(word):
            return True

        if self.visited[i][j]=1:
            return False

        self.visited[i][j]=1
        for direct in self.direction:
            x,y=i+direct[0],j+direct[1]
            if 0<=x<self.m and 0<=y<self.n and self.visited[x][y]==0 and board[x][y]==word[index]:
                print(board[x][y])

                self.findPath(x,y,board,word,index+1)
                self.visited[i][j]=0
        return False