class Solution {
    public static int[] dx = {0,1,0,-1};
    public static int[] dy = {1,0,-1,0};
    //右，下，左，上
    public boolean exist(char[][] board, String word) {
        boolean[][] mark = new boolean[board.length][board[0].length];
        String s = "";
        if (board == null || board.length == 0 || word == null || word.length() == 0) {
            return false;
        }
        for(int i = 0;i<board.length;i++)
        {
            for(int j = 0;j<board[i].length;j++)
            {
                if(board[i][j]==word.charAt(0))
                {
                    int index = 0;
                    if(dfs(i,j,word,board,mark,index+1))
                        return true;
                }
            }
        }
        return false;
    }
    public static boolean dfs(int x,int y,String word,char[][] bord,boolean[][] mark,int index)
    {
        if(index==word.length())
            return true;
        
        mark[x][y] = true;
        for(int i = 0;i<4;i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(cheak(xx,yy,mark))
            {
                if(bord[xx][yy] == word.charAt(index))
                {
                    if(dfs(xx,yy,word,bord,mark,index+1))
                        return true;
                }
            }
        }
        mark[x][y] = false;
        return false;
    }
    public static boolean cheak(int x,int y,boolean[][] mark)//减枝
    {
        if(x<0||x>=mark.length||y<0||y>=mark[0].length||mark[x][y]==true)
            return false;
        return true;
    }
}