【剑指Offer12】矩阵中的路径

【剑指Offer12】矩阵中的路径

矩阵中的路径
题目：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true
方法一：回溯
通常回溯参数为：已知条件、现有条件、状态记录。
方法分为两个部分：终止条件、递归方法
递归过程前需要更新状态，递归过程后需要恢复状态

class Solution {
    boolean ans = false;

    public boolean exist(char[][] board, String word) {
        char begin = word.charAt(0);
        char[][] visit = new char[board.length][board[0].length];
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] == begin) backtrace(board,word,i,j,0,visit);
                if(ans == true) return true;
            }
        }
        return ans;
    }

    public void backtrace(char[][] board, String word,int m, int n, int i,char[][] visit){
        if(visit[m][n] == 0 && word.charAt(i) == board[m][n] && i == word.length() - 1) {
            ans = true;
            return;
        }
        if(word.charAt(i) == board[m][n]){
            visit[m][n] = 1;
            //上下左右
            if(ans == false && m - 1 >= 0 && visit[m - 1][n] == 0) backtrace(board,word,m-1,n,i+1,visit);
            if(ans == false && n - 1 >= 0 && visit[m][n - 1] == 0) backtrace(board,word,m,n-1,i+1,visit);
            if(ans == false && m + 1 < board.length && visit[m + 1][n] == 0) backtrace(board,word,m+1,n,i+1,visit);
            if(ans == false && n + 1 < board[0].length && visit[m][n + 1] == 0) backtrace(board,word,m,n+1,i+1,visit);
            visit[m][n] = 0;
        }
    }
}