import copy
class Solution:
    def exist(self, board, word) -> bool:
        width=len(board[0])
        height=len(board)
        def findletter(subboard,x,y,word):
            if len(word)==0:
                return True
            if x-1>=0:
                if subboard[x-1][y]==word[0]:
                    backup=subboard[x-1][y]
                    subboard[x-1][y]=0
                    if findletter(subboard,x-1,y,word[1:]):
                        return True
                    else:
                        subboard[x - 1][y]=backup
            if x+1<height :
                if subboard[x+1][y]==word[0]:
                    backup=subboard[x+1][y]
                    subboard[x+1][y]=0
                    if findletter(subboard,x+1,y,word[1:]):
                        return True
                    else:
                        subboard[x+1][y]=backup
            if y-1>=0:
                if subboard[x][y-1]==word[0]:
                    backup = subboard[x][y-1]
                    subboard[x][y-1]=0
                    if findletter(subboard,x,y-1,word[1:]):
                        return True
                    else:
                        subboard[x][y-1]=backup
            if y+1<width:
                if subboard[x][y+1]==word[0]:
                    backup=subboard[x][y + 1]
                    subboard[x][y+1]=0
                    if findletter(subboard,x,y+1,word[1:]):
                        return True
                    else:
                        subboard[x][y+1]=backup
            return False
        for i in range(height):
            for j in range(width):
                if board[i][j]==word[0]:
                    subboard=copy.deepcopy(board)
                    subboard[i][j]=0
                    if findletter(subboard,i,j,word[1:]):
                        return True

        return False