机器人运动范围1
需积分: 0 4 浏览量
2022-08-03
15:08:29
上传
评论
收藏 461KB PDF 举报
机器人运动范围
地上有一个 m 行 n 列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]
的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能
进入行坐标和列坐标的数位之和大于 k 的格子。例如，当 k 为 18 时，机器人能够进入方
格 [35, 37] ，因为 3+5+3+7=18。但它不能进入方格 [35, 38]，因为 3+5+3+8=19。请问该机
器人能够到达多少个格子？
示例 ：
输入：m = 2, n = 3, k = 1
输出：3
class Solution {
public:
int movingCount(int m, int n, int k) {
if(k == 0) return 1;
vector<vector<bool> > valid(m, vector<bool>(n, true)); // 记录该位置
是否被访问过
return dfs(valid, m, n, 0, 0, k);
}
int dfs(vector<vector<bool> >& valid, int m, int n, int row, int col, i
nt k) // valid 的传值一定要用 &
{
int sum = getSum(row) + getSum(col);
// 如果越界，或者和大于 k，或者已被访问过了，返回 0
if(row>=m || col>=n || sum>k || !valid[row][col]) return 0;
valid[row][col] = false; // 该位置状态变为：已访问过
return 1 + dfs(valid,m,n,row+1,col,k) + dfs(valid,m,n,row,col+1,k);
// 回溯法（递归）
}
int getSum(int num)
{
// 求某个数字所有位数相加的和
if(num < 10) return num;
int sum = 0;
while(num > 0)
{
sum += num % 10;
num /= 10;
}
return sum;
}
};
扈涧盛
- 粉丝: 24
- 资源: 319
最新资源
- 基于MIC+NE555光敏电阻的声光控电路Multisim仿真原理图
- python tkinter-08-盒子模型.ev4.rar
- Doozy UI Manager 2023
- 基于matlab实现夜间车牌识别程序(1).rar
- 基于matlab实现无线传感器网络无需测距定位算法matlab源代码 包括apit，dv-hop，amorphous在内的共7个
- 基于python的yolov5实现的旋转目标检测
- 基于matlab实现无线传感器网络 CAB定位仿真程序 这是无线传感器节点定位CAB算法的仿真程序，由matlab完成.rar
- 基于matlab实现图像处理，本程序使用背景差分法对来往车辆进行检测和跟踪.rar
- 基于matlab实现视频监控中车型识别代码，自己写的，希望和大家多多交流.rar
- springcodespringcodespringcodespringcode
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0