請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來(lái)判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑窝革。路徑可以從矩陣中任意一格開(kāi)始购城，每一步可以在矩陣中向左、右虐译、上瘪板、下移動(dòng)一格。如果一條路徑經(jīng)過(guò)了矩陣的某一格漆诽，那么該路徑不能再次進(jìn)入該格子侮攀。
解析：該題使用回溯法。由于回溯法基本使用遞歸的寫法厢拭，而總函數(shù)肯定是不能遞歸的兰英，所以我們需要單獨(dú)寫一個(gè)遞歸的核心函數(shù) hasPathCore(...)。先考慮一下應(yīng)該如何回溯：題中要求在矩陣中找到一條符合字符串的路徑蚪腐，所以我們不需要在所有的方塊上進(jìn)行上下左右的搜索箭昵，我們只需要在符合條件的方塊里搜索它的上下左右有沒(méi)有字符串中下一個(gè)字符就好。所以回季，繼續(xù)往下走的條件如下：
- 坐標(biāo)合法
- 該方塊里的字符正是在字符串中需要讀取的字符
- 該方塊之前沒(méi)有被訪問(wèn)過(guò)
- 該方塊的上下左右方塊中有滿足條件的下一個(gè)字符
只要我們能夠一直成功找到一系列的字符家制，并且找完了整個(gè)字符串，那就說(shuō)明該矩陣是滿足題中條件的泡一。這個(gè)就是回溯核心最后的返回值颤殴。如果遇到了部分匹配字符串，但是下一個(gè)就找不到了鼻忠，那就說(shuō)明這條路徑是不可以用的涵但，那就應(yīng)該回退，從上一步重新搜索新的路徑，并把這個(gè)方塊設(shè)置為未訪問(wèn)矮瘟，以免影響未來(lái)的路徑判斷瞳脓。
由于起點(diǎn)可能在矩陣的任意一個(gè)位置，所以我們的總函數(shù)需要在整個(gè)矩陣中遍歷找到起點(diǎn)澈侠。一旦找到了起點(diǎn)劫侧，接下來(lái)從這個(gè)位置四方搜索下一個(gè)字符，直到找到那條路徑哨啃。如果遍歷完了整個(gè)矩陣還沒(méi)找到符合條件的起點(diǎn)烧栋，那就說(shuō)明這個(gè)矩陣不存在這樣的路徑，那就返回 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;
}
