【剑指】76，机器人运动路径（上下左右）

梦里梦外; 2023-05-28 14:20 12阅读 0赞

**题目描述**  
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？  
思路：  
nc，xd  
首先，类似上一题，用一个flag数组记录走过的节点，count做成全局变量。主函数提供接口  
子接口负责从初始点开始四面走，出界或错误，或不满足条件就返回0！

代码：

class Solution { 
    public:
        int count;
        int movingCount(int threshold, int rows, int cols)
        { 
    		count=0;
    		if(rows<=0 ||cols<=0 ||threahold<=0)
    			return count;
    		vector<int>flag(rows*cols,0);		//0代表没有走过
    		count=movingCount(flag,threadhold,rows,cols,0,0);
    		return count;
    	}
     private:
     int  movingCount(vector<int> &flag, int threshold, int rows, int cols,int x,int y )
       { 
       //小于限制即可进入
    	if(!isless(x,y,threshold) ||x>=rows ||y>=cols || x<0 || y<0 || flag[x*cols+y]==1)
    		return 0;
    	flag[x*cols+y]=1;
    	count=1+movingCount(flag, threshold,rows,cols,x-1,y)
                          +movingCount(flag,threshold,rows,cols,x+1,y)
                          +movingCount(flag, threshold,rows,cols,x,y-1)
                           +movingCount(flag, threshold,rows,cols,x,y+1) ;
         return count;            
    	}
     bool isless(int x, int y,int threshold )
        { 
    		 int num=0;
            while(x!=0)
            { 
                num+=x%10;			//取个位
                x=x/10;				//类似右移一位，为了求x的各个数之和
            }
            while(y!=0)
            { 
                num+=y%10;
                y=y/10;
            }
            if(num<=threshold)
                return  true;
            else
                return false;
    	}