矩阵中的路径

矩阵中的路径

思路：DFS+回溯

1、寻找矩阵中的入口

2、深度优先搜索，按照上->右->下->左的顺序

3、当前深度搜索路径不满足要求。回溯，回到上一步。

重复步骤1，2，3，直到找到一条匹配路径退出。

注意事项：需要有一个标记矩阵，标记当前已走过的路径。

代码如下：

class Solution {
public:
    void help(vector matrix, int row, int col, string str){
        if (matrix[row][col] == str[0])
        {
            if (str.size() == 1){
                flag = 1;
                return;
            }
            flagMatrix[row][col] = 1;//标记已走过路径
            //顺时针寻找路径，上->右->下->左
            if (row>0 && flagMatrix[row-1][col] !=1)
                help(matrix, row-1, col, str.substr(1));
            if (col<matrix[0].size()-1 && flagMatrix[row][col+1] !=1)
                help(matrix, row, col+1, str.substr(1));
            if (row<matrix.size()-1 && flagMatrix[row+1][col] !=1)
                help(matrix, row+1, col, str.substr(1));
            if (col>0 && flagMatrix[row][col-1] !=1)
                help(matrix, row, col-1, str.substr(1));
            flagMatrix[row][col] = 0;//回溯
        }
    }
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        vector matrixs;
        string s1 = matrix;
        string s2 = str;
        vector> temp(rows,vector(cols));
        flagMatrix = temp;
        for (int i = 0; i < rows; ++i)
            matrixs.push_back(s1.substr(i*cols,(i+1)*cols));
        for (int i = 0; i < rows; ++i)
        {
            for (int j = 0; j < cols; ++j)
            {
                if (matrixs[i][j] == s2[0])
                {
                    help(matrixs, i, j, s2);
                    if (flag)
                        return true;
                }
            }
        }
        return false;
    }
private:
    vector> flagMatrix;//标记矩阵
    bool flag = false;
};