每日一题 剑指offer（机器人的运动范围）

编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化和锻炼自己的编程能力（最起码不会忘记编程）

特别说明：编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法，所以提供的代码不一定是最优解，但是本文提供的编程代码均为通过测试代码。

机器人的运动范围

题目描述

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

解析

本题可以采用回溯法，把该方格看做是一个m*n的矩阵。在这个矩阵中，除边界上的各子外其他格子都有四个相邻的格子。机器人从坐标（0,0）开始移动。当它准备进入坐标为(i,j)的格子时，通过检查坐标的数位和来判断是否能进入。如果能进入，再接着判断它能否进入四个相邻的格子(i,j-1)、(i-1,j)、(i+1,j)、(i,j+1)。

代码

class Solution {
public:
   int Count(int row, int col){
       int count=0;
       while(row||col){
           count+=row%10+col%10;
           row/=10;
           col/=10;
       }
       return count;
   }
   int movingCount(int threshold, int rows, int cols){
       if((rows<1&&cols<1)||threshold<0)
           return 0;
       int R=1;
       bool* visited=new bool[rows*cols];
       memset(visited,0,rows*cols);
       visited[0]=true;
       stack<int> S;
       S.push(0);
       int p[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
       while(!S.empty()){
           int i=S.top()/cols,j=S.top()%cols;
           S.pop();
           for(int k=0;k<4;k++){
               int row=i+p[k][0],col=j+p[k][1];
               if(row>=0&&row<rows&&col>=0&&col<cols&&!visited[row*cols+col]&&Count(row,col)<=threshold){
                   S.push(row*cols+col);
                   visited[row*cols+col]=true;
                   R++;
               }
           }
       }
       return R;
   }
};