矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子

解题思路

使用回溯思想：

1. 根据给定数组，初始化一个标志位数组，初始化为 false，表示未走过，true 表示已经走过，不能走第二次

2. 根据行数和列数，遍历数组，先找到一个与 str 字符串的第一个元素相匹配的矩阵元素，进入 dfs

3. 根据 i 和 j 先确定一维数组的位置，因为给定的 matrix 是一个一维数组

4. 确定递归终止条件：越界，当前找到的矩阵值不等于数组对应位置的值，已经走过的，这三类情况，都直接 false，说明这条路不通

5. 若 k 已经判断到了最后一位，此时说明是匹配成功的

6. 递归寻找周围四个格子是否符合条件，只要有一个格子符合条件，就继续再找这个符合条件的格子的四周是否存在符合条件的格子，直到k到达末尾或者不满足递归条件就停止

7. 走到这一步，说明本次是不成功的，我们要还原一下标志位数组 index 处的标志位，进入下一轮的判断

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        boolean[] flag = new boolean[matrix.length];
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(dfs(flag, i, j, rows, cols, matrix, str, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    public boolean dfs(boolean[] flag, int i, int j, int rows, int cols, char[] matrix, char[] str, int k) {
        int index = cols * i + j;
        if(i < 0 || j < 0 || i >= rows || j >= cols || flag[index] == true || matrix[index] != str[k]) {
            return false;
        }
        if(k == str.length - 1) {
            return true;
        }
        flag[index] = true;
        if(dfs(flag, i + 1, j, rows, cols, matrix, str, k + 1) ||
           dfs(flag, i - 1, j, rows, cols, matrix, str, k + 1) ||
           dfs(flag, i, j + 1, rows, cols, matrix, str, k + 1) ||
           dfs(flag, i, j - 1, rows, cols, matrix, str, k + 1)) {
            return true;
        }
        flag[index] = false;
        return false;
    }
}