《剑指offer》--013--机器人的运动范围

你的名字 2022-06-01 07:59 122阅读 0赞

[《剑指offer》–目录索引][offer]

**题目：**

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

**思路：**

> 要学会看懂题目的要求：  
> ①只能从(0,0)坐标出发；  
> ②每次移动只能移动到当前位置的上下左右四个位置；  
> ③走过的坐标不能再走；  
> ④不能进入行坐标和列坐标的数位之和大于k的格子  
> 因此，我们采用最合适的回溯递归法

**代码如下：**

RobotMove.h

#ifndef __ROBOTMOVE_H__
    #define __ROBOTMOVE_H__
    
    #include <stdio.h>
    #include <stdlib.h>
    
    int GetDigitSum(int number);//计算一个数各位之和
    
    int MovingCountCore(int row,int col,int rows,int cols,int k,int* HasVisited);//统计移动范围
    
    int MovingCount(int rows,int cols,int k);//统计移动范围
    
    #endif

RobotMove.c

#include "RobotMove.h"
    
    int GetDigitSum(int number)//就算一个数各位之和
    {
        int sum=0;
        while(number != 0)
        {
            sum += number%10;
            number /= 10;
        }
        return sum;
    }
    
    int MovingCount(int rows,int cols,int k)//统计行走范围
    {
        int* HasVisited=(int *)malloc(sizeof(int)*rows*cols);//动态数组保存矩阵每个位置有无被走过的情况
        int i=0;
        for(;i<rows*cols;i++)
        {
            HasVisited[i]=0;//全部初始化为0，代表未被走过
        }
        int count=MovingCountCore(0,0,rows,cols,k,HasVisited);
        free(HasVisited);
        HasVisited=NULL;
        return count;
    }
    
    int MovingCountCore(int row,int col,int rows,int cols,int k,int* HasVisited)//回溯统计移动范围核心代码
    {
        if(row < 0 || col < 0 || row >= rows || col >= cols )//越界
            return 0;
    
        int ret=GetDigitSum(row)+GetDigitSum(col);
        if(ret <= k && HasVisited[row*cols+col] == 0)
        {
            HasVisited[row*cols+col]= 1;//1代表已经走过
            return 1 + MovingCountCore(row-1,col,rows,cols,k,HasVisited)//上
                 + MovingCountCore(row+1,col,rows,cols,k,HasVisited)//下
                 + MovingCountCore(row,col-1,rows,cols,k,HasVisited)//左
                 + MovingCountCore(row,col+1,rows,cols,k,HasVisited);//右
        }
        else
        {
            return 0;
        }
    }

test.c

#include "RobotMove.h"
    
    void test()
    {
        //3行4列
        printf("%d\n",MovingCount(3,4,0));
        printf("%d\n",MovingCount(3,4,1));
        printf("%d\n",MovingCount(3,4,2));
        printf("%d\n",MovingCount(3,4,3));
        printf("%d\n",MovingCount(3,4,4));
        printf("%d\n",MovingCount(3,4,5));
        printf("%d\n",MovingCount(3,4,6));
        printf("%d\n",MovingCount(10,10,5));
    }
    
    int main()
    {
        test();
        return 0;
    }

**运行结果：**  
![这里写图片描述][SouthEast]

[offer]: http://blog.csdn.net/w_y_x_y/article/details/79209805
[SouthEast]: /images/20220601/e6fddcac750a4ee7b0b631398bfb5cb0.png