12-矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

$$ \begin{bmatrix} a & b & c &e \ s & f & c & s \ a & d & e& e\ \end{bmatrix}\quad $$

这道题目的本质就是走迷宫。大家应该都玩过走迷宫的游戏，我们会先从起点开始，然后随便选择一条路，一直走，直到走到出口或者无路可走。假如无路可走了，就回退到上一个路口，这样反复的选择、回退，最终找到出口。

其实回溯的想法就是从走迷宫的过程中提炼出来的，简单的说，啥是回溯？说白了就是撞了南墙咱得回头，然后记住这条路是不通的，咱得换一条路，关键是吃一堑长一智。

回溯一般都会和递归在一起，回溯指代的是题目是属于哪种套路，递归是具体的求解方法。

回溯的框架是

backtrack
   如果节点符合条件
     加入到result中
   for 选择 in 可能的选择
   		进行选择
   		backtrack
   		撤销选择

再说回具体题目，在矩阵中寻找bcced路径，那么需要首先在矩阵中遍历找到b字母，然后以b作为起点，继续向周围撒网式寻找。

详见代码注释

   public boolean exist(char[][] board, String word) {
        if(board == null || word == null){
            return false;
        }
        int rows = board.length;
        int cols = board[0].length;
        //这里初始化一个visited数组，用于标识哪个坐标被访问过了。这个属于回溯算法必备要素之一了。
        boolean[][] visited = new boolean[rows][cols];
        char[] ch = word.toCharArray();
        //下面的两层循环就是将矩阵的每一个坐标作为起点，开始查找。
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if( existCore(board, visited, i, j, ch, 0)){
                    return true;
                }
            }
        }
        return false;
    }
		//这个方法是核心方法，判断在board[row][col]开头的 word[index]作为首字母的情况下，能否找到一条路径。
    private boolean existCore(char[][] board, boolean[][] visited, int row, int col, char[] word, int index) {
        int rows = board.length;
        int cols = board[0].length;
        //假如word字符串已经到尽头了，说明已经匹配完了
        if (index == word.length) {
            return true;
        }
        //这里是验证坐标是否越界 这个判断一定是在上面判断之后的 想想这是为什么？
        if (!isPositionValid(rows, row) || !isPositionValid(cols, col)) {
            return false;
        }
        //假如已经访问过了，那么不应该再访问了
        if (visited[row][col]) {
            return false;
        }
        //如果字符不相等，说明找错了，回退
        if (board[row][col] != word[index]) {
            return false;
        }
        //以上条件都ok了，那么就将这个坐标标记为已经访问过了
        visited[row][col] = true;
        //word[index]匹配了 那么继续匹配下一个字符
        index++;
        //需要从四周开始查找
        boolean flag =  existCore(board, visited, row, col + 1, word, index)
                || existCore(board, visited, row , col - 1, word, index )
                || existCore(board, visited, row - 1, col , word, index)
                || existCore(board, visited, row + 1, col , word, index);
        //如果没有找到 说明[row][col]这个坐标不是路径里的，这个要重新置为没有访问，因为后面别的路径可能会用到 这里容易忘记
        if (!flag) {
            visited[row][col] = false;
        }
        return flag;
    }

    private boolean isPositionValid(int length, int target) {
        return target >= 0 && target < length;
    }