矩阵中的路径

题目

参考链接：

https://www.2cto.com/kf/201610/559087.html
https://blog.csdn.net/u012429555/article/details/90476001

注意

• 传入的是一个一维数组，但是给出了 二维数组的 行 和列，所以要考虑二维转一维的位置问题 int index = i * cols + j;进行二维转一维

代码实现

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        int flag[] = new int[matrix.length];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (helper(matrix, rows, cols, i, j, str, 0, flag))
                    return true;
            }
        }
        return false;
    }
 
    private boolean helper(char[] matrix, int rows, int cols, int i, int j, char[] str, int k, int[] flag) {
        int index = i * cols + j;//进行二维转一维
/*
i < 0 || i >= rows || j < 0 || j >= cols  
      保证数组不越界
matrix[index] != str[k] 
      进行对比，也就是比较矩阵中的当前位置上与str在k位置上的字母是否相同；
      例如 index =0；k=0，就是比较矩阵的第一个与目标中的第一个是否相同，也就是找到开始位置；
      如果遍历矩阵完了还没找到开始位置与目标开始位置一样的字母就可以说这个矩阵中没有这个字符串
flag[index] == 1
      当前位置访问了就是1，没访问就是0
      如果当前位置访问过了，就意味着不可以返回走过的路径
无论哪一项为true
就代表矩阵当前位置与目标字符串当前位置 上的字符 不匹配
*/
        if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index] == 1)
            return false;
        if(k == str.length - 1) return true; //如果上面的条件都不成立，就代表能够找到这样的路径，所有要给出递归的出口，出口就是，目标字符串已经比较到了末尾位置，也就是最后一个位置；
        flag[index] = 1;//如果还没又比较到目标字符串的最末尾位置，就把矩阵的当前位置 置为 1，表明已经访问了 这里只是 **假设当前位置可以走到**
        if (helper(matrix, rows, cols, i + 1, j, str, k + 1, flag)//矩阵往下走一步，同时目标字符串也往后走一个
                || helper(matrix, rows, cols, i - 1, j, str, k + 1, flag)//往上
                || helper(matrix, rows, cols, i, j + 1, str, k + 1, flag)//往右
                || helper(matrix, rows, cols, i, j - 1, str, k + 1, flag)) //往左
            return true;//都比较完了并且能找到这个路径，就返回true
        
        flag[index] = 0;//如果当前位置走着走着走不通了，就把当前位置 假设的1 换为 0； 毕竟1 本来就是假设的，这里就是说重置一下
        return false;//都走不通了，就返回false
    }
}

总结：

跟走迷宫问题差不多 开始位置为任意，比较的地方不一样