题目描述

• 地上有一个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 。

留一个小小的兴趣点

• 能否通过代码一的输出，找出机器人走的路径呢?? (欢迎留言讨论)

• 代码一输出如下