矩阵中的路径

题目描述

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

矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
思路：回溯。 路径的起始位置可以是矩阵中的任何位置，创建数组统计该方格是否被访问。

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        
        if (matrix == NULL || rows < 1 || cols < 1 || str == NULL) {
            return false;
        }
        //创建二维数组
        bool *visited = new bool[rows*cols];
        for (int i = 0; i < rows*cols; i++)
        {
            visited[i] = false;
        }
        //memset(flag, false,rows*cols);

        //字符串的起点可能从字符串的任意位置开始。
        for (int i = 0; i <rows; i++)
        {
            for (int j = 0; j <cols; j++)
            {
                if (isPath(matrix, i, j, rows, cols, 0, str, visited)) {
                    return true;
                }
            }
        }
        delete[] visited;
        return false;

    }
    //当前字符串位置k
    bool isPath(char *matrix,int row,int col,int rows,int cols,int k,char*str,bool *visited) {
        int index = row*cols + col;
        if (col < 0 
            || row<0
            || col>=cols
            || row >= rows
            || matrix[index]!= str[k]
            ||visited[index]==true) {
            return false;
        }
        //判断该该路径是否走完。
        if (str[k + 1] == '\0') {
            return true;
        }
        //进入当前方格，访问状态标记未true
        visited[index]= true;

        if (isPath(matrix, row + 1, col, rows, cols, k + 1, str, visited)
            || isPath(matrix, row - 1, col, rows, cols, k + 1, str, visited)
            || isPath(matrix, row, col + 1, rows, cols, k + 1, str, visited)
            || isPath(matrix, row, col - 1, rows, cols, k + 1, str, visited)
            ) {
            return true;
        }
        //字符串连接当前字符后不与目标字符串匹配，重置当前网格的访问状态
        visited[index] = false;
        //当前字符串与目标字符串不配置
        return false;

    }
};