面试题12：矩阵中的路径
题目要求：
设计一个函数，用来判断一个矩阵中是否存在一条包含某字符串的路径。
（1）起点随意；（2）路径的移动只能是上下左右；（3）访问过的位置不能再访问。以下图矩阵为例，包含“bfce”，但是不包含“abfb”。
a b t g
c f c s
j d e h
解题思路：
本题考察回溯法。
回溯法适合解决由多个步骤组成的问题，且每个步骤都有多个选项。当在某一步选择了其中一个选项，就进入下一步，然后面临新的选项。如果当前的选项已经确定没有正确答案，就回溯到上一步，在上一步选择另一选项，重复进行。回溯法的求解过程一般都可以用树状结构表示出来。实现代码很适合用递归完成。
至于本题，需要明确递归的约束条件，回溯的终止条件，标记矩阵的标记与清除时机。具体可以看下述代码，关键部分已经做了注释。
package chapter2;
/**
* Created by ryder on 2017/7/2.
* 矩阵中的路径
*/
public class P89_StringPathInMatrix {
//回溯法解决
public static boolean hasPath(char[][] data,String str){
if(data==null || data.length==0 || str==null || str.length()==0)
return false;
int rowLen = data.length;
int colLen = data[0].length;
boolean[][] visitFlag = new boolean[rowLen][colLen];
for(int row=0;row<rowLen;row++){
for(int col=0;col<colLen;col++){
visitFlag[row][col] = false;
}
}
for(int row=0;row<rowLen;row++){
for(int col=0;col<colLen;col++){
if(hasPathCore(data,row,col,visitFlag,str,0))
return true;
}
}
return false;
}
public static boolean hasPathCore(char[][] data,int rowIndex,int colIndex,
boolean[][] visitFlag,String str,int strIndex){
//结束条件
if(strIndex>=str.length()) return true;
if(rowIndex<0 || colIndex<0 || rowIndex>=data.length || colIndex>=data[0].length)
return false;
//递归
if(!visitFlag[rowIndex][colIndex]&&data[rowIndex][colIndex]==str.charAt(strIndex)){
//如果未被访问，且匹配字符串，标记当前位置为已访问，分上下左右四个位置递归求解
visitFlag[rowIndex][colIndex] = true;
boolean result =
hasPathCore(data,rowIndex+1,colIndex,visitFlag,str,strIndex+1) ||
hasPathCore(data,rowIndex-1,colIndex,visitFlag,str,strIndex+1) ||
hasPathCore(data,rowIndex,colIndex+1,visitFlag,str,strIndex+1) ||
hasPathCore(data,rowIndex,colIndex-1,visitFlag,str,strIndex+1);
//已经求的结果，无需修改标记了
if(result)
return true;
//当前递归的路线求解失败，要把这条线路上的标记清除掉
//因为其他起点的路径依旧可以访问本路径上的节点。
else{
visitFlag[rowIndex][colIndex] = false;
return false;
}
}
else
return false;
}
public static void main(String[] args){
char[][] data = {
{'a','b','t','g'},
{'c','f','c','s'},
{'j','d','e','h'}};
System.out.println(hasPath(data,"bfce")); //true
System.out.println(hasPath(data,"abfb")); //false,访问过的位置不能再访问
}
}
运行结果
true
false
