题解 | #矩阵中的路径#
矩阵中的路径
http://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param matrix char字符型二维数组
* @param word string字符串
* @return bool布尔型
*/
public boolean hasPath (char[][] matrix, String word) {
// write code here
int n = matrix.length;
int m = matrix[0].length;
int length = word.length();
for(int i = 0;i < n;i ++){
for(int j = 0;j < m;j ++){
if(matrix[i][j] == word.charAt(0)){
if(dfs(i,j,0,n,m,word,matrix)){
return true;
};
}
}
}
return false;
}
public boolean dfs(int i,int j,int index,int n,int m,String word,char[][] matrix){
if(i >= n || i < 0 || j >= m || j < 0 || matrix[i][j] != word.charAt(index)){
return false;
}
if(index == word.length()-1){
return true;
}
char yuan = matrix[i][j];
matrix[i][j] = '#';
boolean isV = dfs(i+1,j,index+1,n,m,word,matrix) ||
dfs(i-1,j,index+1,n,m,word,matrix) ||
dfs(i,j+1,index+1,n,m,word,matrix) ||
dfs(i,j-1,index+1,n,m,word,matrix);
matrix[i][j] = yuan;
return isV;
}
}