請設計一個函數(shù)，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中任意一格開始，每一步可以在矩陣中向左、右、上、下移動一格。如果一條路徑經(jīng)過了矩陣的某一格，那么該路徑不能再次進入該格子。

解析：該題使用回溯法。由于回溯法基本使用遞歸的寫法，而總函數(shù)肯定是不能遞歸的，所以我們需要單獨寫一個遞歸的核心函數(shù) hasPathCore(...)。先考慮一下應該如何回溯：題中要求在矩陣中找到一條符合字符串的路徑，所以我們不需要在所有的方塊上進行上下左右的搜索，我們只需要在符合條件的方塊里搜索它的上下左右有沒有字符串中下一個字符就好。所以，繼續(xù)往下走的條件如下：

• 坐標合法
• 該方塊里的字符正是在字符串中需要讀取的字符
• 該方塊之前沒有被訪問過
• 該方塊的上下左右方塊中有滿足條件的下一個字符

只要我們能夠一直成功找到一系列的字符，并且找完了整個字符串，那就說明該矩陣是滿足題中條件的。這個就是回溯核心最后的返回值。如果遇到了部分匹配字符串，但是下一個就找不到了，那就說明這條路徑是不可以用的，那就應該回退，從上一步重新搜索新的路徑，并把這個方塊設置為未訪問，以免影響未來的路徑判斷。

由于起點可能在矩陣的任意一個位置，所以我們的總函數(shù)需要在整個矩陣中遍歷找到起點。一旦找到了起點，接下來從這個位置四方搜索下一個字符，直到找到那條路徑。如果遍歷完了整個矩陣還沒找到符合條件的起點，那就說明這個矩陣不存在這樣的路徑，那就返回 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;
}