package leetcode;

public class demo_79 {
    //全局变量，如果找到就返回
    int flag=0;
    public boolean exist(char[][] board, String word) {
        int[][] visited=new int[board.length][board[0].length];
        for(int i=0;i<board.length;i++) {
            for(int j=0;j<board[0].length;j++) {
                visited[i][j]=0;
            }
        }
        for(int i=0;i<board.length;i++) {
            for(int j=0;j<board[0].length;j++) {
                backtrack(board, visited, word, i, j, 0);
                if(flag==1) {return true;}
            }
        }
        return false;
    }
    public void backtrack(char[][] board,int[][] visited,String word,int i,int j,int index) {
        if(board[i][j]==word.charAt(index)) {
            if(visited[i][j]==0) {
                //记录当前位置是否被访问过
                visited[i][j]=1;
                //满足条件，则返回
                if(index==word.length()-1) {flag=1;return;}
                if(index<word.length()-1) {
                    //向左搜索
                    if(flag==0&&i-1>-1) {backtrack(board, visited, word, i-1, j, index+1);}
                    //向右搜索
                    if(flag==0&&i+1<board.length) {backtrack(board, visited, word, i+1, j, index+1);}
                    //向上搜索
                    if(flag==0&&j-1>-1) {backtrack(board, visited, word, i, j-1, index+1);}
                    //向下搜索
                    if(flag==0&&j+1<board[0].length) {backtrack(board, visited, word, i, j+1, index+1);}
                }
                visited[i][j]=0;
            }
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        demo_79 d79=new demo_79();
        char[][] board= {{‘A‘,‘B‘,‘C‘,‘E‘},{‘S‘,‘F‘,‘C‘,‘S‘},{‘A‘,‘D‘,‘E‘,‘E‘}};
        String word="ABCCED";
        System.out.println(d79.exist(board, word));
    }

}