题目描述
- 地上有一个m行和n列的方格。
- 一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于
k 的格子。
- 例如，当 k 为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
考虑回退情况
题目解读
- 剑指Offer 92
- 这道题第一次做的时候，没明白题目意思，导致代码写出来了，但是和题目不符
- 简单说一下我是如何走偏的，通过书中解读，知道机器人是可以回退的(这点没想到)，比如四个小方格，坐标为(0,0)、(0,1)、(1,0)、(1,1)，你说符合题目意思，机器人可以走几个格子呢? 正确答案是三个，(0,0)、(0,1)、(1,0)，有同学可能会问了，机器人从(0,0) -> (0, 1)，咋到(1, 0)啊，其实机器人可以回到(0, 0),再走到(1, 0)..
- 我第一次做的时候直接不考虑回退，即考虑只能向前走，当然了，如果不考虑机器人回退的话，则答案是2，即只能走(0, 0),(0, 1) 或者 (0,0),(1,0)这两条路.
本篇文章考虑回退情况对进行分析下一篇文章对不考虑回退情况进行分析
代码
- 代码有两种实现方式 <二维数组 vs 一维数组>
- 一、将二维格子存放在二维数组中
#include<iostream>
#include<string.h>
using namespace std;
#define threshold 3
#define rows 5
#define cols 5
class Solution {
public:
int add_row_col(int loc){
int tt = 0;
while(loc > 0){
tt += loc%10;
loc /= 10;
}
return tt;
}
int movingCountCore(int row, int col, int visited[][cols]){
int a[4];
int result = 0;
memset(a, 0, 4*sizeof(int));
if(visited[row][col] == 0 && add_row_col(row) + add_row_col(col) <= threshold){
visited[row][col] = 1;
// 上
if(row > 0){
a[0] = movingCountCore(row-1, col, visited);
}
// 下
if(row < rows-1){
a[1] = movingCountCore(row+1, col, visited);
}
// 左
if(col > 0){
a[2] = movingCountCore(row, col-1, visited);
}
// 右
if(col < cols-1){
a[3] = movingCountCore(row, col+1, visited);
}
result = 1 + a[0] + a[1] + a[2] + a[3];
cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<endl;
}
else{
result = 0;
}
return result;
}
int movingCount(){
int visited[rows][cols];
memset(visited, 0, sizeof(int)*rows*cols);
int bb = movingCountCore(0, 0, visited);
for(int i=0; i < rows; i++){
for(int j=0; j < cols; j++){
cout<<visited[i][j]<<" ";
}
cout<<endl;
}
return bb;
}
};
int main()
{
Solution ss;
cout<<ss.movingCount()<<endl;
}
#include<iostream>
#include<string.h>
using namespace std;
class Solution {
public:
int add_row_col(int loc){
int tt = 0;
while(loc > 0){
tt += loc%10;
loc /= 10;
}
return tt;
}
int movingCountCore(int threshold, int rows, int cols, int row, int col, int *visited){
int a[4];
int result = 0;
memset(a, 0, 4*sizeof(int));
if(visited[row * cols + col] == 0 && add_row_col(row) + add_row_col(col) <= threshold){
visited[row * cols + col] = 1;
// 上
if(row > 0){
a[0] = movingCountCore(threshold, rows, cols, row-1, col, visited);
}
// 下
if(row < rows-1){
a[1] = movingCountCore(threshold, rows, cols, row+1, col, visited);
}
// 左
if(col > 0){
a[2] = movingCountCore(threshold, rows, cols, row, col-1, visited);
}
// 右
if(col < cols-1){
a[3] = movingCountCore(threshold, rows, cols, row, col+1, visited);
}
result = 1 + a[0] + a[1] + a[2] + a[3];
}
else{
result = 0;
}
return result;
}
int movingCount(int threshold, int rows, int cols){
if(threshold < 0 || rows <= 0 || cols <= 0){
return 0;
}
int visited[rows*cols];
memset(visited, 0, sizeof(int)*rows*cols);
return movingCountCore(threshold, rows, cols, 0, 0, visited);
}
};
int main()
{
Solution ss;
int threshold = 5;
int rows = 10;
int cols = 10;
cout<<ss.movingCount(threshold, rows, cols)<<endl;
}
总结展望
- 代码一和代码二实现的功能都是一样的，只是说实现方式不一样而已。
- 题目非常好，值得深入思考
- 本文是考虑机器人可以回退的情况，欢迎查阅下一篇机器人不考虑回退情况下，最多能到达多少个格子?
知识点
-
memset 此函数用来初始化操作，在 #include<string.h> 库文件中
- void *memset(void *s, int ch, size_t n);
- 函数解释：将s中当前位置后面的n个字节 （typedef unsigned int size_t ）用 ch 替换并返回 s 。
留一个小小的兴趣点
- 能否通过代码一的输出，找出机器人走的路径呢?? (欢迎留言讨论)
-
代码一输出如下
