首页 / 面试 / 面试题13：机器人的运动范围（C++）
面试题13：机器人的运动范围（C++）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了面试题13：机器人的运动范围（C++），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3379字，纯文字阅读大概需要5分钟。
内容图文
题目地址：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
题目描述
地上有一个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
示例 2：
输入：m = 3, n = 1, k = 0
输出：1
提示：
1 <= n,m <= 100
0 <= k <= 20
解题思路
矩阵搜索问题，可用广度优先搜索或者深度优先搜索策略解决，因为是从左上角到右下角，所以只需向下和向右即可到达，不需要向上和向左。
机器人的运动范围需要同时满足以下两个条件：
- 当前格子坐标数位之和小于等于 k；
- 从坐标（0，0）出发，通过上下左右移动可到达当前格子。
BFS：广度优先搜索使用队列解决问题，我们将每个还未搜索到的点一次性放入队列中，然后弹出队列的头部元素当作当前遍历的节点。BFS在，若不需要确定当前遍历到具体层数，则模板如下
while(队列queue不为空)
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未访问过：
queue.push(该节点)
如果需要确定当前遍历到哪一层，即步数或二叉树的的层数则模板如下
层数level = 0
while(队列queue不为空）
队列中元素个数size = queue.size() //需要向前移动的节点个数
while (size --) {
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未被访问过：
queue.push(该节点)
}
层数level ++;
在本题中，我们并不需要记录遍历的层数，只需统计总的遍历多少个点即可，我们使用visited记录一个点是否遍历过。
DFS：深度优先搜索通过递归，先朝着一个方向搜索到底，再回溯至上个节点，沿另一个方向搜索，依次类推。在本题中，我们用数组visited来存储每个元素是否已被访问，一般的时候，我们是从上下左右四个方向行走，但分析本题可发现，从下和右两个方向前行，所以，我们最后使用dfs(x + 1, y, m, n, k) + dfs(x, y + 1, m, n, k) + 1来返回向下和向右走的数目。需要注意的一点是剪枝条件，在搜索中，遇到数位和超出目标值、此元素已访问，则应立即返回，即可行性剪枝。这里我们剪枝的条件设置为当前节点已被访问或该元素下标溢出，以及行坐标x和列坐标y的数位和(即个位+十位)大于k。
程序源码
BFS
class Solution {
public:
int visited[100][100];
int step = 0;
int movingCount(int m, int n, int k) {
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
visited[i][j] = 0; //初始化，所有元素均未访问
}
}
queue<pair<int,int>> que;
que.push({0, 0});
visited[0][0] = 1; //已访问
int dir_x[] = {0, 0, -1, 1}; //x方向坐标
int dir_y[] = {-1, 1, 0, 0}; //y方向坐标
while(!que.empty())
{
auto front = que.front();
que.pop();
int x = front.first;
int y = front.second;
step++;
for(int i = 0; i < 4; i++)
{
int new_x = x + dir_x[i];
int new_y = y + dir_y[i];
if(new_x < 0 || new_y < 0 || visited[new_x][new_y] == 1 || new_x >= m || new_y >= n || (new_x / 10 % 10 + new_x % 10 + new_y / 10 % 10 + new_y % 10) > k) continue;
que.push({new_x, new_y});
visited[new_x][new_y] = 1;
}
}
return step;
}
};
DFS
class Solution {
public:
int visited[100][100];
int step = 0;
int movingCount(int m, int n, int k) {
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
visited[i][j] = 0; //未访问
}
}
return dfs(0, 0, m, n, k);
}
int dfs(int x, int y, int m, int n, int k)
{
if(visited[x][y] == 1 || x >= m || y >= n || (x / 10 % 10 + x % 10 + y / 10 % 10 + y % 10) > k) return 0;
visited[x][y] = 1; //已访问
step = dfs(x + 1, y, m, n, k) + dfs(x, y + 1, m, n, k) + 1;
return step;
}
};
参考文章
内容总结
以上是互联网集市为您收集整理的面试题13：机器人的运动范围（C++）全部内容，希望文章能够帮你解决面试题13：机器人的运动范围（C++）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。