題目描述

• 地上有一個(gè)m行和n列的方格。
• 一個(gè)機(jī)器人從坐標(biāo)0,0的格子開始移動(dòng)，每一次只能向左，右，上，下四個(gè)方向移動(dòng)一格，但是不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于 k 的格子。
• 例如，當(dāng) k 為18時(shí)，機(jī)器人能夠進(jìn)入方格（35,37），因?yàn)?+5+3+7 = 18。但是，它不能進(jìn)入方格（35,38），因?yàn)?+5+3+8 = 19。請問該機(jī)器人能夠達(dá)到多少個(gè)格子？
• 考慮回退情況

題目解讀

• 劍指Offer 92
• 這道題第一次做的時(shí)候，沒明白題目意思，導(dǎo)致代碼寫出來了，但是和題目不符
• 簡單說一下我是如何走偏的，通過書中解讀，知道機(jī)器人是可以回退的(這點(diǎn)沒想到)，比如四個(gè)小方格，坐標(biāo)為(0,0)、(0,1)、(1,0)、(1,1)，你說符合題目意思，機(jī)器人可以走幾個(gè)格子呢? 正確答案是三個(gè)，(0,0)、(0,1)、(1,0)，有同學(xué)可能會(huì)問了，機(jī)器人從(0,0) -> (0, 1)，咋到(1, 0)啊，其實(shí)機(jī)器人可以回到(0, 0),再走到(1, 0)..
• 我第一次做的時(shí)候直接不考慮回退，即考慮只能向前走，當(dāng)然了，如果不考慮機(jī)器人回退的話，則答案是2，即只能走(0, 0),(0, 1) 或者 (0,0),(1,0)這兩條路.
• 本篇文章考慮回退情況對進(jìn)行分析
• 下一篇文章對不考慮回退情況進(jìn)行分析

代碼

• 代碼有兩種實(shí)現(xiàn)方式 <二維數(shù)組 vs 一維數(shù)組>
• 一、將二維格子存放在二維數(shù)組中

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

• 二、將二維格子存放在一維數(shù)組中

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

總結(jié)展望

• 代碼一和代碼二實(shí)現(xiàn)的功能都是一樣的，只是說實(shí)現(xiàn)方式不一樣而已。
• 題目非常好，值得深入思考
• 本文是考慮機(jī)器人可以回退的情況，歡迎查閱下一篇機(jī)器人不考慮回退情況下，最多能到達(dá)多少個(gè)格子?

知識(shí)點(diǎn)

• memset 此函數(shù)用來初始化操作，在 #include<string.h> 庫文件中
• void *memset(void *s, int ch, size_t n);
• 函數(shù)解釋：將s中當(dāng)前位置后面的n個(gè)字節(jié) （typedef unsigned int size_t ）用 ch 替換并返回 s 。

留一個(gè)小小的興趣點(diǎn)

• 能否通過代碼一的輸出，找出機(jī)器人走的路徑呢?? (歡迎留言討論)

• 代碼一輸出如下