題目描述
請設(shè)計一個函數(shù)，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑辜贵。路徑可以從矩陣中的任意一個格子開始归形，每一步可以在矩陣中向左，向右厚棵，向上蔼紧，向下移動一個格子。如果一條路徑經(jīng)過了矩陣中的某一個格子彬犯，則該路徑不能再進(jìn)入該格子查吊。 例如 a b c e s f c s a d e e 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑卢佣，因?yàn)樽址牡谝粋€字符b占據(jù)了矩陣中的第一行第二個格子之后箭阶，路徑不能再次進(jìn)入該格子。
這是一道典型的回溯法解決的題目嘹叫，任選一個格子A作為起點(diǎn)诈乒，判斷其周圍的點(diǎn)是否滿足字符串序列要求，若點(diǎn)B滿足則繼續(xù)在B的周圍尋找下一個字符喂饥，若點(diǎn)B不滿足則回退到A肠鲫，查找其他節(jié)點(diǎn)。注意矩陣邊上點(diǎn)的臨界判斷捞高。由于路徑不能重復(fù)進(jìn)入矩陣的格子，所以還需要設(shè)置一個標(biāo)志矩陣來記錄進(jìn)入過的矩陣格子氢哮。
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
boolean[] flag = new boolean[matrix.length];
//初始化標(biāo)志矩陣
for(int i = 0; i < flag.length; i++) {
flag[i] = true;
}
//遍歷每一個格子型檀，找到第一個存在要求路徑的格子時停止
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(hasNext(matrix, rows, cols, str, i, j, 0, flag)) {
return true;
}
}
}
return false;
}
private boolean hasNext(char[] matrix, int rows, int cols, char[] str, int i, int j, int k, boolean[] flag) {
int index = i * cols + j;
//矩陣邊上格子的限定贱除，i媳溺、j的限定要在index之前，否則index會溢出
if(i >= rows || i < 0 || j < 0 || j >= cols || matrix[index] != str[k] || flag[index] == false) {
return false;
}
if(k == str.length - 1) {
return true;
}
//將進(jìn)入過的節(jié)點(diǎn)進(jìn)行標(biāo)記
flag[index] = false;
if(hasNext(matrix, rows, cols, str, i + 1, j, k + 1, flag) ||
hasNext(matrix, rows, cols, str, i - 1, j, k + 1, flag) ||
hasNext(matrix, rows, cols, str, i, j + 1, k + 1, flag) ||
hasNext(matrix, rows, cols, str, i, j - 1, k + 1, flag)) {
return true;
}
//若不符合條件扯躺，將標(biāo)記釋放蝎困，以便于回退后仍可進(jìn)入該格子
flag[index] = true;
return false;
}
}
