【剑指Offer】面试题13. 机器人的运动范围
2024-09-05 19:51:44
题目
地上有一个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。请问该机器人能够到达多少个格子?
示例 1:
输入:m = 2, n = 3, k = 1
输出:3
示例 1:
输入:m = 3, n = 1, k = 0
输出:1
提示:
- 1 <= n,m <= 100
- 0 <= k <= 20
思路
深度优先。
代码
class Solution {
public:
int movingCount(int m, int n, int k) {
int cnt = 0;
vector<bool> visited(m * n);
dfs(m, n, 0, 0, k, cnt, visited);
return cnt;
}
void dfs(int m, int n, int i, int j, int k, int &cnt, vector<bool> &visited) {
if (i < 0 || i >= m || j < 0 || j >= n || visited[i * n + j]) return;
if (helper(i) + helper(j) > k) return;
++cnt;
visited[i * n + j] = true;
dfs(m, n, i - 1, j, k, cnt, visited);
dfs(m, n, i + 1, j, k, cnt, visited);
dfs(m, n, i, j - 1, k, cnt, visited);
dfs(m, n, i, j + 1, k, cnt, visited);
}
int helper(int num) {
int res = 0;
while (num) {
res += num % 10;
num /= 10;
}
return res;
}
};
最新文章
- 使用spring的AOP时产生的异常
- Word中的字体大小
- CodeForces 219C Color Stripe
- JQuery validate 在IE兼容模式下出现 js错误(成员找不到)的修正:
- JS正则表达式基础总结
- [原]Unity3D深入浅出 - 导航网格自动寻路(Navigation Mesh)
- Javascript编程模式(JavaScript Programming Patterns)Part 1.(初级篇)
- 关于Redis
- 简单字符串处理 hdu2532 Engine
- AOP 之 6.1 AOP基础 ——跟我学spring3(转)
- nginx与apache配合反向代理技术1
- jQuery开发自定义插件 $.extend()与$.fn.extend()
- cordova闪屏插件插件使用:cordova-plugin-splashscreen
- 将php-fpm添加至service服务
- asp.net利用存储过程分页代码
- IDEA 导出项目war包
- GDI+编程(画笔/画刷/路径/区域)
- MySQL的ALTER变更、正则查询、分组查询、排序查询以及事务查询的概
- iframe父窗口和子窗口之间的调用
- 〖Linux〗Ubuntu13.10,在终端打开gvim提示“GLib-GObject-WARNING”的临时解决办法
热门文章
- 新见Java数据类型_需了解
- Keras入门——(6)长短期记忆网络LSTM(三)
- Linux centosVMware vim 编辑模式、vim命令模式、vim实践
- 转:NGINX 基于nginx_upstream_check_module-master 健康检测及平滑升级
- Python可视化 | Seaborn包—heatmap()
- LeetCode刷题--基础知识篇--KMP算法
- php 投票系统
- 题解 CF1131C 【Birthday】
- VUE - 路由跳转时设置动画效果
- Noip2018普及组初赛试题解题报告