矩阵中的路径

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        boolean[] visited = new boolean[matrix.length];
        for(int row =0;row < rows;row++){
            for(int col =0;col<cols;col++){
                if(hasPathCore(matrix,rows,cols,row,col,str,0,visited)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean hasPathCore(char[] matrix, int rows, int cols, int row,int col,char[] str,int k,boolean[] visitFlags){
        int index = row * cols + col;//求出当前在哪
        if(row < 0 || col<0 || row>=rows || col >=cols || visitFlags[index] || matrix[index] != str[k]){
            return false;
        }
        visitFlags[index] = true;
        if(k == str.length-1){
            return true;
        }
        k++;
        if(hasPathCore(matrix,rows,cols,row+1,col,str,k,visitFlags) || 
           hasPathCore(matrix,rows,cols,row-1,col,str,k,visitFlags) ||
           hasPathCore(matrix,rows,cols,row,col+1,str,k,visitFlags) ||
           hasPathCore(matrix,rows,cols,row,col-1,str,k,visitFlags)){
            return true;
        }
        visitFlags[index] = false;
        return false;
    }
}

题目

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

 

思路

这是一个可以用回溯法解决的典型问题。

首先，遍历这个矩阵，我们很容易就能找到与字符串str中第一个字符相同的矩阵元素ch。然后遍历ch的上下左右四个字符，如果有和字符串str中下一个字符相同的，就把那个字符当作下一个字符（下一次遍历的起点），如果没有，就需要回退到上一个字符，然后重新遍历。为了避免路径重叠，需要一个辅助矩阵来记录路径情况。

下面代码中，当矩阵坐标为（row，col）的格子和路径字符串中下标为pathLength的字符一样时，从4个相邻的格子（row，col-1）、（row-1，col）、（row，col+1）以及（row+1，col）中去定位路径字符串中下标为pathLength+1的字符。

如果4个相邻的格子都没有匹配字符串中下标为pathLength+1的字符，表明当前路径字符串中下标为pathLength的字符在矩阵中的定位不正确，我们需要回到前一个字符串（pathLength-1），然后重新定位。

一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到格式的位置（此时str[pathLength] == '\0'）。

 

 public static void main(String[] args) {
        char[] matrix = { 'a','b','c','e','s','c','s','a','d','e','e' };
        char[] str ={'b','c','c','e','d'};
        System.out.println(hasPath(matrix,3,4,str));
    }
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        boolean visitFlags[] = new boolean[matrix.length];
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (hasPathCore(matrix, rows, cols, row, col, str, 0, visitFlags))
                {
                    return true;
                }
            }
        }
        return false;
    }
/**
     * 回溯法递归实现判断
     * @param matrix    字符矩阵
     * @param rows  矩阵行数
     * @param cols  矩阵列数
     * @param row   当前行索引
     * @param col   当前列索引
     * @param str   目标字符序列
     * @param k 目标字符序列中当前字符索引
     * @param visitFlags    字符矩阵是否被访问过标记
     * @return
     */
    public boolean hasPathCore(char[] matrix, int rows, int cols, int row, int col, char[] str,  int k, boolean[] visitFlags) {
        //这个是重点
        int index = row * cols + col;
        //index就是在该矩阵中的值
        //这个是重点
        // 行列索引超限、当前字符已经被访问过、当前字符不等于目标字符序列的当前字符，直接返回false
        if (row < 0 || col < 0 || row >= rows || col >= cols || 
                visitFlags[index] || matrix[index] != str[k])
        {
            return false;
        }
        visitFlags[index] = true;   // 设置访问标记
        if (k == str.length - 1)    // 递归结束条件，k已经到达目标字符序列的最后一个字符
        {
            return true;
        }
        k++;    // 匹配目标字符序列的下一个字符
 
        // 在当前字符的上、下、左、右的元素搜索下一个目标字符，递归
        if (hasPathCore(matrix, rows, cols, row + 1, col, str, k, visitFlags) || 
                hasPathCore(matrix, rows, cols, row - 1, col, str, k, visitFlags) || 
                hasPathCore(matrix, rows, cols, row, col + 1, str, k, visitFlags) || 
                hasPathCore(matrix, rows, cols, row, col - 1, str, k, visitFlags))
        {
            return true;
        }
        // // 在当前字符的上、下、左、右的元素没有搜索到下一个目标字符，将访问标记重置为false，返回false；
        visitFlags[index] = false;
        return false;
    }
 public static void main(String[] args) {
        char[] matrix = { 'a','b','c','e','s','f','c','s','a','d','e','e' };
        char[] str ={'b','c','c','e','d'};
        System.out.println(hasPath(matrix,3,4,str));
    }