经典DFS题解 | #矩阵中的路径#

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix char字符型二维数组
* @param word string字符串
* @return bool布尔型
*/
public boolean hasPath (char[][] matrix, String word) {
// write code here
char[]words = word.toCharArray();
for(int i = 0; i<matrix.length; i++){
for(int j = 0; j<matrix[0].length; j++){
if(dfs(matrix,words,i,j,0)) return true;
}
}
return false;
}
public boolean dfs(char[][]matrix, char[]words, int i, int j, int k){
if(i>=matrix.length||i<0||j<0||j>=matrix[0].length||matrix[i][j]!=words[k]){
return false;
}
//原地修改不需要额外空间
matrix[i][j] = '\0';
if(k == words.length-1){
return true;
}
boolean res = dfs(matrix,words,i,j+1,k+1)||dfs(matrix,words,i+1,j,k+1)||dfs(matrix,words,i,j-1,k+1)|| dfs(matrix,words,i-1,j,k+1);
//改回来
matrix[i][j] = words[k];
return res;
}
}