package offer;
/**
*
* 矩阵是否包含某路径
*
* 矩阵：
* [a b t g
* c f c s
* j d e h]
*
* 路径：b f c e
*
*/
public class PathInJuZhen {
public static void main(String[] args) {
int rows =
3;
int cols =
4;
String juZhen =
"abtgcfcsjdeh";
String find =
"bfce";
if(findPath(juZhen, find, rows, cols)) {
System.out.print(
"find");
}
}
public static boolean findPath(String juZhen, String find,
int rows,
int cols) {
boolean[] flag =
new boolean[juZhen.length()];
for (
int i =
0; i < rows; i++) {
for (
int j =
0; j < cols; j++) {
if (hasPath(juZhen, find, rows, cols, i , j,
0, flag)) {
return true;
}
}
}
return false;
}
private static boolean hasPath(String juZhen, String find,
int rows,
int cols,
int i,
int j,
int k,
boolean[] flag) {
int index = i * cols + j;
if (i <
0 || i > rows || j <
0 || j > rows || juZhen.charAt(index) != find.charAt(k) || flag[index]) {
return false;
}
if (find.length() -
1 == k) {
return true;
}
flag[index] =
true;
if (
hasPath(juZhen, find, rows, cols, i -
1 , j, k +
1, flag)
|| hasPath(juZhen, find, rows, cols, i +
1 , j, k +
1, flag)
|| hasPath(juZhen, find, rows, cols, i , j -
1, k +
1, flag)
|| hasPath(juZhen, find, rows, cols, i , j +
1, k +
1, flag)
) {
return true;
}
return false;
}
}
