剑指offer: 机器人的运动范围

灰太狼 2022-02-25 15:35 180阅读 0赞

## 题目描述 ##

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

解题思路：

用一个二维数组记录每个点是否已经访问过，BFS统计可以访问的每个点

class Solution {
    public:
        int movingCount(int threshold, int rows, int cols)
        {
            vector<vector<bool>> flag(rows,vector<bool> (cols,false));
            
            return moving(threshold, rows, cols, 0, 0, flag);
        }
        int moving(int threshold, int rows, int cols, int i, int j, vector<vector<bool>>& flag) {
            int count = 0;
            if(i < 0 || i >= rows ||  j < 0 || j >= cols || getsum(i) + getsum(j) > threshold || flag[i][j] == true)    //不统计的情况
                return 0;
            
            flag[i][j]= true;    //已访问
            count = 1 + moving(threshold, rows, cols, i + 1, j, flag)
                      + moving(threshold, rows, cols, i - 1, j, flag)
                      + moving(threshold, rows, cols, i, j - 1, flag)
                      + moving(threshold, rows, cols, i, j + 1, flag);
            return count;
        }
        
        int getsum(int num) {
            int sum = 0;
            while(num) {
                sum += num % 10;
                num /= 10;
            }
            return sum;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer 机器人的运动范围

[剑指offer题型分类及各题的解题思路与代码（<---点我跳转 ^ - ^）][offer_---_ _ -] 题目描述地上有一个m行和n列的方...

梦里梦外;/ 2024年04月17日 16:09/ 0 赞/ 89 阅读

相关剑指 Offer 13. 机器人的运动范围

题目地上有一个m行n列的方格，从坐标 \[0,0\] 到坐标 \[m-1,n-1\] 。一个机器人从坐标 \[0, 0\] 的格子开始移动，它每次可以向左、右、上、下移

￡神魔★判官ぃ/ 2022年12月17日 03:27/ 0 赞/ 131 阅读

相关剑指 Offer 13. 机器人的运动范围

题目：地上有一个m行n列的方格，从坐标 \[0,0\] 到坐标 \[m-1,n-1\] 。一个机器人从坐标 \[0, 0\] 的格子开始移动，它每次可以向左、右、上、下移

谁借莪１个温暖的怀抱￠/ 2022年12月07日 01:49/ 0 赞/ 124 阅读

相关【剑指Offer】13. 机器人的运动范围

[NowCoder][] 题目描述地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动，每一次只能向左右上下四个方向移动一格，但是不能进

比眉伴天荒/ 2022年11月25日 00:38/ 0 赞/ 143 阅读

相关剑指offer_机器人的运动范围

/ 机器人的运动范围：地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能

妖狐艹你老母/ 2022年06月10日 11:56/ 0 赞/ 196 阅读

相关剑指Offer-机器人的运动范围

题目描述地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。

傷城~/ 2022年05月22日 03:10/ 0 赞/ 204 阅读

相关剑指offer: 机器人的运动范围

题目描述地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。

灰太狼/ 2022年02月25日 15:35/ 0 赞/ 181 阅读

相关剑指Offer-机器人的运动范围

题目描述地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。

小鱼儿/ 2022年02月04日 01:23/ 0 赞/ 209 阅读

相关剑指Offer 13 机器人的运动范围

[机器人的运动范围][Link 1] 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标

墨蓝/ 2021年12月19日 04:19/ 0 赞/ 180 阅读

相关剑指offer：机器人的运动范围

试题：地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例

心已赠人/ 2021年06月24日 16:10/ 0 赞/ 363 阅读