剑指Offer(牛客版)--面试题13:机器人的运动范围

剑指Offer(牛客版)--面试题13:机器人的运动范围

 


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

 

完整代码:

 

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
         //检查输入的合法性
        if(threshold<0||rows<=0||cols<=0)
            return 0;
        // 创建一个访问情况的矩阵
        bool* Visited = new bool[rows*cols];
        //将矩阵初始化为false
        memset(Visited, 0,rows*cols);
        //计算可以到达的格子数,从(0,0)位置开始
        int count=movingCountCore(threshold, rows, cols, 0, 0,Visited);
        //删除辅助空间
        delete[] Visited;
        
        //返回最终可达到的格子数
        return count;
    }
private:
    int movingCountCore(int threshold, int rows, int cols, int row, int col, bool* Visited)
    {
        //计数
        int count=0;
        //检查当前格子是否可以进入
        if(check(threshold, rows, cols, row, col, Visited))
        {
            //标记当前点已经访问过
            Visited[row*cols+col] = true;
            
            //紧接着向上/下/左/右方向搜寻可达到的格子数
            count = 1+ movingCountCore(threshold, rows, cols, row-1, col, Visited)
                + movingCountCore(threshold, rows, cols, row+1, col, Visited)
                + movingCountCore(threshold, rows, cols, row, col-1, Visited)
                + movingCountCore(threshold, rows, cols, row, col+1, Visited);
        }
        //返回最终可以到达的格子数
        return count;
    }
    //检查当前格子是否可以进入
    bool check(int threshold, int rows, int cols, int row, int col, bool* Visited)
    {
        //判断当前点是否在合适的范围、行列坐标的数位之和不大于k的格子且没有被范访问过
        if(row>=0&&row<rows&&col>=0&&col<cols&&getDigitSum(row)+getDigitSum(col)<=threshold&&!Visited[row*cols+col])
            return true;
        else
            return false;
    }
    //求行位数和列位数之和
    int  getDigitSum(int number)
    {
        int sum = 0;
        while (number>0)
        {
            //求最低位的数字之和
            sum +=number%10;
            //去除最低位
            number /=10;
        }
        //返回行位数和列位数之和
        return sum;
    }
};

 

上一篇:如何在二维numpy数组中对向量[u,v]设置阈值?


下一篇:Udacity无人驾驶工程师试看课——车道线检测观后感