剑指65-矩阵中的路径

深度遍历，着重复盘

题目描述

{assert_img 1.png 1.png}

解法

虽说是使用深度遍历，但是我没想好要怎么判断字符串是否匹配，所以一下代码时题解看到的，巧妙的时，使用两个数组可以表示上下左右的元素，而且不需要额外数组表示是否遍历过，将遍历过的位置用一个特殊字符’#’替换

代码

class Solution {
public:
    int col,row; //定义全局变量
    bool hasPath(char* matrix, int rows, int cols, char* str){ //char* matrix 二维数组用一维数组表示
        col = cols, row = rows; //为全局变量赋值
        for (int i = 0;i < rows;i ++) //先遍历二维数组
            for (int j = 0;j < cols; j ++)
                if (dfs(matrix, str, 0,i,j)) return true; //查找第一个字符位置，若存在路径则返回true，否则继续循环，查找下个字符
        return false;
    }
    bool dfs(char* matrix, char* str, int u, int x, int y) {
        if (u == strlen(str)) return true; //如果字符串的长度等于搜索长度u则返回true
        if (matrix[x*col+y] != str[u]) return false; //如果有元素不等则返回false
        int dx[4] = {-1, 0, 1, 0},dy[4] = {0, 1, 0, -1}; //(-1,0)up,(0，1)right,(1,0)down,(0,-1)left
        char t = matrix[x*col+y]; //将访问过的路径字符赋值给t
        matrix[x*col+y] = '*'; //将访问国的路径赋值为'*'
        for(int i = 0; i < 4; i ++){
            int a = x +dx[i],b = y +dy[i]; //进行上、下、左、右变化后的x，y值
            if(dfs(matrix, str, u + 1, a, b)) return true;
        }
        matrix[x*col+y] = t; //将访问过值放回原矩阵
        return false;
    }
};