public class Solution {
     public boolean exist(char[][] board, String word) {
        if(board.length == 0) return false;
        int leni = board.length;
        int lenj = board[0].length;
        boolean[][] isVisited = new boolean[leni][lenj];
        for(int i=0;i < leni;++i){
            for(int j = 0; j < lenj;++j){
                isVisited[i][j]= false;
            }
        }
        
        for(int i = 0; i < leni;++i){
            for(int j = 0 ; j < lenj;++j){
                if(board[i][j] == word.charAt(0))
                {
                    isVisited[i][j] = true;
                    if(WordSearch(board,isVisited,word.substring(1),i,j)){
                        return true;
                    }
                    isVisited[i][j] = false;
                }
            }
        }
        return false;
        
    }
    
    public boolean WordSearch(char[][] board,boolean[][] isVisited,String word,int i, int j){
        if(word.length() == 0) return true;
        int[][] direction={{0,1},{0,-1},{-1,0},{1,0}};//上下左右
        for(int k = 0; k < direction.length;++k){
            
            int x = i + direction[k][0];
            int y = j + direction[k][1];
            if((x >= 0 && x < board.length) &&
               (y >= 0 && y < board[i].length) &&
               board[x][y] == word.charAt(0)&&
               isVisited[x][y] == false){
                isVisited[x][y] = true;
                if(WordSearch(board,isVisited,word.substring(1), x,  y)){
                    return true;
                }
                isVisited[x][y] = false;
            }
            
        }
        return false;
    }
}