剑指66-机器人运动的范围

opencode

发布于 2022-12-26 14:33:17

1570

发布于 2022-12-26 14:33:17

文章被收录于专栏：知识同步

深度遍历，着重复盘

题目描述

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

解法

这个可以用深度遍历，只不过比之前的多了一个条件，就是要符合条件的各自才能走

好久没写了，忘了一个很重要的东西，导致我debug了半天，传递的参数要想可以改变，参数必须是引用或者指针或者引用指针，一般是引用和引用指针多一点

代码

class Solution {
public:
    int cal(int num)
    {
        int sum = 0;

        while (num) {
            sum += (num % 10);
            num /= 10;
        }

        return sum;
    }

    int movingCount(int threshold, int rows, int cols)
    {
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        int count = 0;
        move(threshold, 0, 0, rows, cols, count, visited);
        return count;
    }

    void move(int threshold, int rows, int cols, int m, int n, int &count, vector<vector<bool>> &judge)
    {
        if (rows >= 0 && rows < m && cols >= 0 && cols < n && (cal(rows) + cal(cols)) <= threshold && !judge[rows][cols]) {
            cout << count << endl;
            count++;
            judge[rows][cols] = true;
        }
        else return;
        move(threshold, rows - 1, cols, m, n, count, judge);
        move(threshold, rows, cols + 1, m, n, count, judge);
        move(threshold, rows + 1, cols, m, n, count, judge);
        move(threshold, rows, cols - 1, m, n, count, judge);
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-11-23，如有侵权请联系 cloudcommunity@tencent.com 删除

机器人