面试题12：矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
主要思想：
- 一个一维数组visited用于存储格子中的数字是否被访问过，主方法遍历每一个格子，去判断这个格子能否获取到路径（另一个方法，该格子能获取到路径，返回true）。
- 获取路径的方法hasPathCore，判断当前的格子的内容是否和路径的当前未访问过的第一个字符相同，并且当前格子没有被访问过，如果为true，路径的当前索引+1，设置当前格子被访问，然后去递归查找该格子的上下左右格子有没有路径，如果没有找到路径，说明以当前格子开头失败，所以回退，设置路径的索引-1，设置当前格子没有被访问过。最后返回是否找到路径的bool值。
<script>
//matrix是一个一维数组，path是路径字符串
function hasPath(matrix, rows, cols, path)
{
if(matrix==null||rows<1||cols<1||path==null)
return false;
// write code here
//用数组存元素是否被访问过，访问过的就不能再访问了，数组的大小就是行*列
let visited=new Array(rows*cols);
//用来保存path字符串的索引
let pathIndex=0;
//通过遍历每个各自，判断是否能找到路径
for(let row=0;row<rows;row++){
for(let col=0;col<cols;col++){
//如果这个格子能够找到路径就会返回true
if(hasPathCore(matrix,rows,cols,row,col,visited,pathIndex,path))
return true;
}
}
return false;
}
//判断这个格子作为起点能不能构成path
function hasPathCore(matrix,rows,cols,row,col,visited,pathIndex,path){
//如果pathIndex已经是path的长度了，说明已经构成了path，返回true。
if(pathIndex===path.length)
return true;
let haspath=false;
//如果这个格子和路径中pathIndex值相同，并且这个格子没有被访问过，表示找到了
if(row>=0&&row<rows&&col>=0&&col<cols&&matrix[row*cols+col]===path[pathIndex]&&!visited[row*cols+col])
{
//给pathIndex++
pathIndex++;
//设置这个格子被访问过
visited[row*cols+col]=true;
//递归的在左右上下格子查找路径
haspath=hasPathCore(matrix,rows,cols,row-1,col,visited,pathIndex,path)||
hasPathCore(matrix,rows,cols,row+1,col,visited,pathIndex,path)||
hasPathCore(matrix,rows,cols,row,col-1,visited,pathIndex,path)||
hasPathCore(matrix,rows,cols,row,col+1,visited,pathIndex,path);
//如果找不到,这个格子作为起点就不行，就当作没有用过，这条路径不通
if(!haspath){
pathIndex--;
visited[row*cols+col]=false;
}
}
return haspath;
}
</script>
面试题13：机器人的运动范围
其实这一题并没有回溯
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
主要思想：从0.0点开始，用一个数组去存格子是否被访问过，然后判断这个格子是否满足条件，如果满足，
设置格子被访问过，递归求count=1+上下左右可到达的格子数。
<script>
function movingCount(threshold, rows, cols) {
if(threshold==null||rows<=0||cols<=0)
return false;
//定义一个数组用于存储格子是否被访问过
let visited=new Array(rows*cols).fill(false);
//方法返回所有的格子数
return moveingCountCore(threshold, rows, cols, 0, 0, visited);
}
//从0，0点开始，格子数就是1+当前格子上下左右格子的
function moveingCountCore(threshold, rows, cols, row, col, visited) {
let count=0;
//检查当前格子是否可达，是否满足坐标位数之和小于k
if(check(threshold, rows, cols, row, col, visited)){
//如果是，就将格子设置为已经被访问
visited[row*cols+col]=true;
//对于这个格子的可访问格子数就是上下左右可访问格子数之和
count=1+moveingCountCore(threshold, rows, cols, row-1, col, visited)+
moveingCountCore(threshold, rows, cols, row+1, col, visited)+
moveingCountCore(threshold, rows, cols, row, col-1, visited)+
moveingCountCore(threshold, rows, cols, row, col+1, visited);
}
return count;
}
function check(threshold, rows, cols, row, col, visited) {
return row >= 0 && row < rows && col >= 0 && col < cols && getDigitSum(row) + getDigitSum(col) <= threshold &&
visited[row * cols + col] === false;
}
function getDigitSum(number) {
let str=number.toString();
let sum=0;
for(let i=0;i<str.length;i++){
sum=sum+parseInt(str[i]);
}
return sum;
}
