题目描述

• 地上有一个m行和n列的方格。
• 一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
• 例如，当 k 为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

题目解读

• 接着上一篇继续深挖这道题目
• 上一篇是考虑机器人可以回退的情况，本篇呢，我们不考虑机器人可以回退的情况，即机器人只能向前，不能回退(不能走已经走过的格子)，这种情况下最多能走多少个格子?
• 比如四个小方格，坐标为(0,0)、(0,1)、(1,0)、(1,1)，只考虑只能向前走，如果不考虑机器人回退的话，即只能走(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];
        // a[0] = 0; 
        // a[1] = 0;
        // a[2] = 0;
        // a[3] = 0;
        memset(a, 0, 4*sizeof(int));
        int result = -1;
        

        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);
            }


            for(int i=0; i < 4; i++){
                if(result < a[i]){
                    result = a[i];
                }
            }

            result += 1;

        }
        else{
            result = 0;
        }

        return result;
    }

    int movingCount(){
        int visited[rows][cols];

        for(int i=0; i < rows; i++){
            for(int j=0; j < cols; j++){
                visited[i][j] = 0;
            }
        }
        return movingCountCore(0, 0, visited);
    }
};

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);
            }


            for(int i=0; i < 4; i++){
                if(result < a[i]){
                    result = a[i];
                }
            }
            result += 1;
        }
        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;
}

• 考虑 threshold = 3, rows = 5, cols = 5 的情况，可得机器人的一条前进路线如图所示(最长路线不唯一)，共计 8

总结展望

• 多思考、多总结、多反思。
• 将两者对比思考，将会发现两者实现思路何其相似，改动也不大，但是实现的任何是不同的.
• 有点游戏的编程感觉在其中，比如遇到墙不能走之类的...