AcWing 23. 矩阵中的路径(Java)__DFS
原题链接
中等
作者:
差一点睡死了
,
2021-01-26 16:39:52
,
所有人可见
,
阅读 330
class Solution {
public boolean hasPath(char[][] matrix, String str) {
for(int i=0;i<matrix.length;i++) {
for(int j=0;j<matrix[0].length;j++) {
if(matrix[i][j]==str.charAt(0)) { //找到第一个相同的字符 在深度遍历
if(dfs(matrix,str,i,j,0)) {
return true;
}
}
}
}
return false;
}
public boolean dfs(char[][] matrix, String str,int x,int y,int level) {
if(matrix[x][y]!=str.charAt(level)) {
return false; //单词不匹配
}
if(level==str.length()-1) {
return true; //已经遍历到字符串后一个字母了
}
int[] dx= {0,-1,0,1},dy= {1,0,-1,0};
char t=matrix[x][y]; //取出正在比较的值进行标记
matrix[x][y]='#';
for(int i=0;i<4;i++) {
int a=x+dx[i],b=y+dy[i];
if(a>=0&&a<matrix.length&&b>=0&&b<matrix[0].length&&matrix[a][b]!='#') {
if(dfs(matrix,str,a,b,level+1)) return true;
}
}
matrix[x][y]=t;
return false;
}
}