机器人的运动范围

最新推荐文章于 2025-05-26 16:38:55 发布

ChenyutingZJU

最新推荐文章于 2025-05-26 16:38:55 发布

阅读量106

点赞数

分类专栏：剑指offer 文章标签：剑指offer

本文链接：https://blog.csdn.net/chenyutingdaima/article/details/89293451

版权

剑指offer 专栏收录该内容

64 篇文章

订阅专栏

本文详细解析了一种机器人运动范围的算法，旨在计算机器人在特定条件下可以到达的格子数量。机器人从坐标(0,0)出发，在m行n列的方格中移动，每次只能向上下左右移动一格，但不能进入行坐标和列坐标数位之和大于k的格子。通过深度优先搜索算法，遍历所有可能路径并标记已访问过的格子，最终统计可达格子的数量。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

机器人的运动范围

题目描述

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

解题思路

只要从(0,0)为起点遍历，对每个位置访问其四周，标记数组标记是否被访问过
对每个合法的位置，接着对他的四周进行访问

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];
        memset(visited,false,rows*cols);
        //只从(0,0)位置开始遍历
        int ans=func(threshold,rows,cols,0,0,visited);
        delete[] visited;
        return ans;
    }
    int func(int threshold,int rows,int cols,int i,int j,bool* visited){
        int cnt=0;
        //没有出界&&当前位置未访问&&当前行列坐标数位之和不大于k
        if(i>=0&&j>=0&&i<rows&&j<cols && visited[i*cols+j]==false&&digitsum(i)+digitsum(j)<=threshold){
            visited[i*cols+j] = true;
            cnt = 1+func(threshold,rows,cols,i+1,j,visited)
                +func(threshold,rows,cols,i-1,j,visited)
                +func(threshold,rows,cols,i,j+1,visited)
                +func(threshold,rows,cols,i,j-1,visited);
        }
        return cnt;
    }
    //计算数位之和
    int digitsum(int a){
        int sum=0;
        while(a>0){
            sum=sum+a%10;
            a/=10;
        }
        return sum;
    }
};