AcWing 23. 矩阵中的路径_JS
原题链接
中等
作者:
cyb-包子
,
2021-05-19 14:49:18
,
所有人可见
,
阅读 287
分析
- 上下左右可以使用数组
- 为了不往回头走,可以改变之前的
matrix[x][y]
但是记得回溯改回去
Code
/**
* @param {character[][]} matrix
* @param {string} str
* @return {boolean}
*/
var hasPath = function(matrix, str) {
function dfs (matrix, str, u, x, y) {
if(matrix[x][y] !== str[u]) return false;
if(u === str.length - 1) return true;
let dx = [-1, 0, 1, 0];
let dy = [0, 1, 0, -1];
let t = matrix[x][y]; //存下来
matrix[x][y] = '*';
for(let i = 0; i < 4; i ++){
let a = x + dx[i];
let b = y + dy[i];
if(a >= 0 && a < matrix.length && b >= 0 && b < matrix[0].length) {
if(dfs(matrix,str,u+1,a,b)) return true;
}
}
matrix[x][y] = t;
return false;
}
for(let i = 0; i < matrix.length; i ++){
for(let j = 0; j < matrix[0].length; j ++){
if(dfs(matrix,str,0,i,j)) return true;
}
}
return false;
};