面试题12：矩阵中的路径

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

解析：该题使用回溯法。由于回溯法基本使用递归的写法，而总函数肯定是不能递归的，所以我们需要单独写一个递归的核心函数 hasPathCore(...)。先考虑一下应该如何回溯：题中要求在矩阵中找到一条符合字符串的路径，所以我们不需要在所有的方块上进行上下左右的搜索，我们只需要在符合条件的方块里搜索它的上下左右有没有字符串中下一个字符就好。所以，继续往下走的条件如下：

• 坐标合法
• 该方块里的字符正是在字符串中需要读取的字符
• 该方块之前没有被访问过
• 该方块的上下左右方块中有满足条件的下一个字符

只要我们能够一直成功找到一系列的字符，并且找完了整个字符串，那就说明该矩阵是满足题中条件的。这个就是回溯核心最后的返回值。如果遇到了部分匹配字符串，但是下一个就找不到了，那就说明这条路径是不可以用的，那就应该回退，从上一步重新搜索新的路径，并把这个方块设置为未访问，以免影响未来的路径判断。

由于起点可能在矩阵的任意一个位置，所以我们的总函数需要在整个矩阵中遍历找到起点。一旦找到了起点，接下来从这个位置四方搜索下一个字符，直到找到那条路径。如果遍历完了整个矩阵还没找到符合条件的起点，那就说明这个矩阵不存在这样的路径，那就返回 false。

答案：

bool hasPathCore(const char* matrix, int rows, int cols, int r,
                 int c, const char* str, int& pathLen, bool* visited)
{
    if (str[pathLen]=='\0') return true;

    bool exist = false;
    if (!visited[r * cols + c] && str[pathLen]==matrix[r * cols + c]
      &&r>=0 && c>=0 && r<rows && c<cols)
    {
        ++pathLen;
        visited[r * cols + c] = true;
        exist =
              hasPathCore(matrix, rows, cols, r, c+1, str, pathLen, visited) ||
              hasPathCore(matrix, rows, cols, r+1, c, str, pathLen, visited) ||
              hasPathCore(matrix, rows, cols, r, c-1, str, pathLen, visited) ||
              hasPathCore(matrix, rows, cols, r-1, c, str, pathLen, visited);
        if (!exist)
        {
            --pathLen;
            visited[r * cols + c] = false;
        }
    }
    return exist;
}

bool hasPath(const char* matrix, unsigned int rows,
        unsigned int cols, const char* str)
{
    if (matrix==nullptr || rows<=0 || cols<=0 || str==nullptr) return false;
    int pathLen = 0;

    bool *visited = new bool[cols * rows];
    memset(visited, 0, cols * rows);

    for (int r = 0; r < rows; ++r)
        for (int c = 0; c < cols; ++c)
        {
            bool has = hasPathCore(matrix, rows, cols, r, c,
                    str, pathLen, visited);
            if (has) return true;
        }
    delete[] visited;

    return false;
}