网站建设公司首选,瑞昌市建设局网站,做问卷调查的网站有啥,网络营销的步骤文章目录 机器人的运动范围描述示例1示例2示例3示例4思路完整代码 机器人的运动范围
描述
地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动#xff0c;每一次只能向左#xff0c;右#xff0c;上#xff… 文章目录 机器人的运动范围描述示例1示例2示例3示例4思路完整代码 机器人的运动范围
描述
地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动每一次只能向左右上下四个方向移动一格但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如当 threshold 为 18 时机器人能够进入方格 [35,37] 因为 3537 18。但是它不能进入方格 [35,38] 因为 3538 19 。请问该机器人能够达到多少个格子
数据范围 0 ≤ t h r e s h o l d ≤ 15 0≤threshold≤15 0≤threshold≤15 $1≤rows,cols≤100 $
进阶空间复杂度 O ( n m ) O(nm) O(nm) 时间复杂度 $O(nm) $
示例1
输入
1,2,3返回值
3示例2
输入
0,1,3返回值
1示例3
输入
10,1,100返回值
29说明 [0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种后面的[0,29],[0,30]以及[0,31]等等是无法到达的 示例4
输入
5,10,10返回值
21思路
最容易想到的方法肯定就是遍历对二维数组的每一位进行遍历但需要考虑当数组下标不是一位数时需要取出每一位进行相加
public int movingCount(int threshold, int rows, int cols) {int count 0;for (int i 0; i rows; i) {for (int j 0; j cols; j) {int sum 0;if (i 10) {while (i 0) {sum i % 10;i / 10;}} else {sum i;}if (j 10) {while (j 0) {sum j % 10;j / 10;}} else {sum j;}if (sum threshold) {count;}}}return count;
}但这种情况下对于较大规模的数据容易超时
下面使用递归来解决这个问题
首先需要定义一个数组access用于记录当前元素是否已经访问过从左上角元素开始递归每次递归先判断是否达到边界条件 超过矩阵边界直接返回横纵坐标数位之和大于threshold直接返回当前节点已访问直接返回 如果未访问过当前节点则结果加一并表姐当前节点为已访问接着递归当前节点的四个邻居节点直到递归结束
完整代码
import java.util.*;
public class Solution {boolean[][] access;int result 0;public int movingCount(int threshold, int rows, int cols) {access new boolean[rows][cols];BackTracking(threshold, 0, 0);return result;}public void BackTracking(int threshold, int row, int col) {if (row 0 || col 0 || row access.length || col access[0].length) {return;}if (cal(row, col) threshold) {return;}if (access[row][col] false) {result;access[row][col] true;} else {return;} BackTracking(threshold, row 1, col);BackTracking(threshold, row, col - 1);BackTracking(threshold, row, col 1);BackTracking(threshold, row - 1, col);return;}public int cal(int row, int col) {int sum 0;while (row 0) {sum row % 10;row row / 10;}while (col 0) {sum col % 10;col col / 10;}return sum;}
}
