原题链接
描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如$$ \begin{bmatrix} a & b & c &e \ s & f & c & s \ a & d & e& e\ \end{bmatrix}$$ 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
示例
输入：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"
返回值：true
思路
DFS。要求矩阵的路径，首先知道起点可能在矩阵中任何一个格子，所以需要遍历所有格子找到word的第一个字符，然后开始深搜诸葛匹配word的各个字符，每次往上下所有四个方向探索，如果对应格子的元素不等于当前word待匹配的字符或者当前格子不合法（数组越界）都说明当前路径不存在，当搜索到word最后一个字符时表示成功。每次从一个格子开始搜索时，都要先把该格子标记为已遍历，以便于从该格子出发的搜索不会再重复搜索到该格子，最后如果没有找到路径的话，要恢复格子原来的元素。
解答
public class Solution {
public boolean hasPath(char[][] matrix, String word) {
// write code here
char[] chars = word.toCharArray();
// 七点不一定是 （0，0）
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (dfs(matrix, chars, i, j, 0)) return true;
}
}
return false;
}
public boolean dfs(char[][] matrix, char[] chars, int i, int j, int k) {
// 如果越界、不匹配
if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || matrix[i][j] != chars[k]) return false;
// 一旦走到下面的就说明当前 matrix[i][j] == chars[k]
// 搜完了
if (k == chars.length - 1) return true;
//开始搜索
// 标记已经遍历的东西
matrix[i][j] = ‘\0‘;
boolean res = dfs(matrix, chars, i + 1, j, k + 1) || dfs(matrix, chars, i, j + 1, k + 1) ||
dfs(matrix, chars, i - 1, j, k + 1) || dfs(matrix, chars, i, j - 1, k + 1);
// 搜索回退
matrix[i][j] = chars[k];
return res;
}
}