欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

面试题13:机器人的运动范围

程序员文章站 2022-06-25 16:22:56
题目:地上有一个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动,它每次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7=18。但它不能进入方格(35,38),因为3+5+3+8=19。请问该机器人能够到达多少个格子?int movingCount(int threshold,int rows,int cols){ if(threshold<0||rows<=0||cols&...

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

int movingCount(int threshold,int rows,int cols)
{
    if(threshold<0||rows<=0||cols<=0)
        return 0;

    bool *visited=new bool[rows*cols];
    for(int i=0;i<rows*cols;i++)
        visited[i]=false;

    int count=movingCountCore(threshold,rows,cols,0,0,visited);

    delete[] visited;
    return count;
}

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,col-1,visited)+
                movingCountCore(threshold,rows,cols,row+1,col,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)
{
    if(row>=0&&row<rows&&col>=0&&col<cols&&getDigitSum(row)+getDigitSum(col)<=threshold&&!visited[row*cols+col])
        return true;
    return false;
}

int getDigitSum(int number)
{
    int sum=0;
    while(number>0)
    {
        sum+=number%10;
        number/=10;
    }
    return sum;
}

本文地址:https://blog.csdn.net/weixin_42729072/article/details/107893992