回溯法矩阵中的路径

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

　　这是一个可以用回溯法解决的经典题。首先，在矩阵中任选一个格子作为路径的起点。假设矩阵中某个格子的字符为ch，并且这个格子将对应于路径上的第i个字符。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的第i个位置。如果路径上的第i个字符正好是ch，那么到相邻的格子寻找路径上得到第i+1个字符。除矩阵边界上的格子之外，其他格子都有4个相邻的格子。重复这个过程，直到路径上的所有字符都在矩阵中找到相应的位置。

　　由于回溯法的递归特性，路径可以被看成一个栈。当在矩阵中定位了路径的前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这时候只好在路径上回到第n-1个字符，重新定位第n个字符。

　　由于路径不能重复进入矩阵的格子，所以还需要定义和字符串矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入了每个格子。

下面的代码实现了这个回溯算法：

bool hasPath(char* matrix, int rows, int cols, char* str)
{//matrix为存放数据的数组（即题目中给的矩阵），str是目标字符串
    if (matrix == NULL || rows < 1 || cols < 1 || str == NULL)
    {
        return false;
    }
    bool* visited = new bool[rows*cols];//定义一个布尔矩阵 
    memset(visited, 0, rows* cols);//把数组中的所有值都赋为0
    int pathLength = 0;//指示目标字符串的下标
    for (int row = 0; row < rows; row++)//行
    {
        for (int col; col < cols; col++)//列
        {
            if (hasPathCore(matrix, rows, cols, row, col, str, pathLength, visited))
            {
                return true;
            }
        }
    }
    delete[]visited;
    return false;
}
bool hasPathCore(const char* matrix, int rows, int cols, int row, int col, const char* str, int& pathLength, bool* visited)
{
    if (str[pathLength] == '')
    {
        return true;
    }
    bool hasPath = false;
    //递归的时候如果匹配就进入，不匹配直接return
    if (row >= 0 && row < rows&&col >= 0 && col < cols&&matrix[row*cols + col] == str[pathLength] && !visited[row*cols + col])
    {
        ++pathLength;
        visited[row*cols + col] = true;//走过后就把值改为true，则不能再进入了
        //四个方向都可以走，使用递归的思想，如果匹配就一直递归下去，如果不匹配就跳出递归
        hasPath = hasPathCore(matrix, rows, cols, row, col - 1, str, pathLength, visited) || hasPathCore(matrix, rows, cols, row - 1, col, str, pathLength, visited) || hasPathCore(matrix, rows, cols, row, col + 1, str, pathLength, visited) || hasPathCore(matrix, rows, cols, row + 1, col, str, pathLength, visited);
        if (!hasPath)//回退，如果下一步四个方向都没有匹配的字符，就退回上一步
        {
            --pathLength;//退回上一步需要把字符串的下标回跳一位
            visited[row*cols + col] = false;//同时需要把所在的这一步的值重新赋为false
        }
    }
    return hasPath;
}

　　当矩阵中坐标为(row,col)的格子和路径字符串中下标为pathLength的字符串一样时，从四个相邻的格子（row，col-1）、（row，col+1）、（row+1，col）、（row-1，col）

中去定位路径字符串中下标为pathLength+1的字符串。

　　如果4个相邻的格子都没有匹配字符串中下标为pathLength+1的字符，则表明当前路径字符串中下标为pathLength的字符在矩阵中的定位不确定，我们需要回到前一个字符（pathLength-1），然后重新定位。

　　一直重复这个过程，直到路径字符串上的所有字符都在矩阵中找到合适的位置（此时str[pathLength]==‘’）

回溯法 矩阵中的路径

回溯法矩阵中的路径