剑指offer 矩阵中的路径

题目描述

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

 

思路：

二维矩阵转化为一维矩阵：i * (列数) + 当前列。

这是道搜索题目，深度优先搜索，在矩阵中搜索等于字符串。记住开始点可以是任意位置，这里使用两个for循环进行遍历。在使用一个helper函数，记住DFS是之前改变的状态一定要在后面改变回来。搜索过的字符设置为‘0’，改变回来的时候等于字符串的对应字符。

class Solution {
public:
    bool helper(char* matrix, int rows, int cols, char* str,int i,int j,int idx){
        if(idx == strlen(str)){
            return true;
        }
        bool result = false;
        if(!(i >= 0 && j >= 0 && matrix[i * cols + j] == str[idx])){
            return false;
        }            
        
        matrix[i * cols + j] = '0';
        result = helper(matrix,rows,cols,str,i + 1,j,idx + 1) ||
                helper(matrix,rows,cols,str,i - 1,j,idx + 1) ||
                helper(matrix,rows,cols,str,i,j + 1,idx + 1) ||
                helper(matrix,rows,cols,str,i,j - 1,idx + 1);            
        matrix[i * cols + j] = str[idx];
        return result;
    }
    bool hasPath(char* matrix, int rows, int cols, char* str){
        if(matrix == nullptr || rows <= 0 || cols <= 0 || str == nullptr){
            return false;
        }
        
        int idx = 0;
        for(int i = 0;i < rows;++i){
            for(int j = 0;j < cols;++j){
                if(helper(matrix,rows,cols,str,i,j,idx)){
                    return true;
                }
            }
        }
        return false;
    }

};