面试题13：机器人的运动范围 - 好文

面试题13：机器人的运动范围 <https://www.cnblogs.com/BoqianLiu/p/9439319.html>
// 面试题13：机器人的运动范围 // 题目：地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移动，它 //
每一次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和 // 大于k的格子。例如，当k为18时，机器人能够进入方格(35,
37)，因为3+5+3+7=18。 // 但它不能进入方格(35, 38)，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
解题思路：

还是和面试题12一样的回溯算法，只不过这个比12题简单多了。

这里明面给出的限制条件只有一个，就是格子的各位之和不可以超过某个给定的数值。

首先准备进入0行0列，当准备进入i行j列的时候，先进行条件的判断，

如果条件符合，就进去，然后上下左右继续尝试，直到尝试到最后一个格子。

其实有一个隐含的条件，就是不可以两次重复进入一个格子，

所以这次我们同样需要一个bool类型的数组来记录是否已经选中了某个格子。

什么？你问那些不符合条件而没被选中的会不会一直遍历下去？

当然不会，条件都不符合，连走的机会都不给他^_^

c/c++：
//计算机器人可以到达格子数 int movingCount(int limitation, int rows, int cols) { //参数有效性校验
if (limitation < 0 || rows <= 0 || cols <= 0) return 0; //初始化标记数组 bool* visited
= new bool[rows*cols]; memset(visited, false, rows*cols); //尝试进入0行0列的格子 int
count = movingCountCore(limitation, rows, cols, 0, 0, visited); //释放内存并返回
delete[] visited; return count; } //回溯算法核心 int movingCountCore(int limitation,
int rows, int cols, int row, int col, bool* visited) { int count = 0;
//可以进入当前的格子 if (check(limitation, rows, cols, row, col, visited)) { //标记格子已经走过
visited[row*cols + col] = true; //尝试向上下左右走出一步 count = 1 +
movingCountCore(limitation, rows, cols, row, col - 1, visited) +
movingCountCore(limitation, rows, cols, row, col + 1, visited) +
movingCountCore(limitation, rows, cols, row - 1, col, visited) +
movingCountCore(limitation, rows, cols, row + 1, col, visited); } return count;
} //校验是否可以进入某个格子 bool check(int limitation, int rows, int cols, int row, int
col, bool* visited) { //行列合法，符合限制条件，且未走过 if (row >= 0 && row < rows&&col >= 0
&& col < cols && !visited[row*cols + col] && getSum(row) + getSum(col) <=
limitation) return true; return false; } //计算某个数字各位之和 int getSum(int number) {
int sum = 0; while (number > 0) { sum += number % 10; number /= 10; } return
sum; }
参考资料：
剑指offer第二版面试题13
<https://github.com/zhedahht/CodingInterviewChinese2/tree/master/13_RobotMove>
posted @2018-08-07 20:42 朕蹲厕唱忐忑 <https://www.cnblogs.com/BoqianLiu/> 阅读(...) 评论(
...) 编辑 <https://i.cnblogs.com/EditPosts.aspx?postid=9439319> 收藏
<https://blog.csdn.net/qq_33296651/article/details/86177099#>

热门工具换一换