矩阵中的路径
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。 ***
思路
比较典型的dfs+回溯模板题。以前做的比较多，直接就出来了。 先定义一个boolean数组，来表示每个方格是否被走过。 然后找出矩阵中与字符串首字母相等的格子开始dfs。 每次check是否找到矩阵外部，与当前格子是否被走过，还有当前格子是否符合字串要求。 符合了即继续dfs，因不知道从哪个方向来，所以四个方向都试一次，如果回头也会因为boolean数组直接返回。 等四个方向都找完了，就回退一步，把当前结点重新置为false，以便其他走法路过。 最后找完了就返回true。
Java实现
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
boolean flag[]=new boolean[matrix.length];
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(matrix[i*cols+j]==str[0]){
if(dfs(matrix, rows, cols, i, j, str, 0, flag)){
return true;
}
}
}
}
return false;
}
private boolean dfs(char[] matrix, int rows, int cols, int i, int j, char[] str, int k, boolean[] flag) {
int index=i*cols+j;
if (i<0||i>=rows||j<0||j>=cols||matrix[index]!=str[k]||flag[index]==true)
return false;
if(k==str.length-1) return true;
flag[index]=true;
if (dfs(matrix, rows, cols, i - 1, j, str, k + 1, flag)
|| dfs(matrix, rows, cols, i + 1, j, str, k + 1, flag)
|| dfs(matrix, rows, cols, i, j - 1, str, k + 1, flag)
|| dfs(matrix, rows, cols, i, j + 1, str, k + 1, flag)) {
return true;
}
flag[index]=false;
return false;
}
}
