机器人的运动范围（JZ13）

尘觉

于 2024-08-10 13:22:57 发布

阅读量710

点赞数 30

分类专栏： # 算法分析文章标签：机器人算法 java 教程开发语言牛客

本文为博主原创文章，未经博主允许不得转载。

本文链接：https://blog.csdn.net/apple_67445472/article/details/141089570

版权

算法分析专栏收录该内容

87 篇文章

订阅专栏

😀前言
在这道题目中，我们需要计算一个机器人在给定的网格范围内，能够到达的最大格子数。机器人每次只能在网格中上下左右移动一格，并且受到一个约束条件的限制：机器人只能进入数位之和小于等于给定阈值的格子。因此，问题的关键是如何在遍历所有可能的格子时，判断是否满足这一条件。使用深度优先搜索（DFS）来进行遍历是解决该问题的一种有效方法。

🏠个人主页：尘觉主页

文章目录

❤️‍🔥机器人的运动范围

❤️‍🔥机器人的运动范围

牛客网

🥰题目描述

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

例如，当 k 为 18 时，机器人能够进入方格 (35,37)，因为 3+5+3+7=18。但是，它不能进入方格 (35,38)，因为 3+5+3+8=19。请问该机器人能够达到多少个格子？

数据范围：
0≤threshold≤15 ，1≤rows,cols≤100

进阶：空间复杂度 O(nm) ，时间复杂度 O(nm)

示例1

输入：1,2,3
返回值：3

示例2

输入：0,1,3
返回值：1

示例3

输入：10,1,100
返回值：29
说明：[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种，后面的[0,29],[0,30]以及[0,31]等等是无法到达的

示例4

输入：5,10,10
返回值：21

💯解题思路

使用深度优先搜索（Depth First Search，DFS）方法进行求解。回溯是深度优先搜索的一种特例，它在一次搜索过程中需要设置一些本次搜索过程的局部状态，并在本次搜索结束之后清除状态。而普通的深度优先搜索并不需要使用这些局部状态，虽然还是有可能设置一些全局状态。

private static final int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
private int cnt = 0;
private int rows;
private int cols;
private int threshold;
private int[][] digitSum;

public int movingCount(int threshold, int rows, int cols) {
    this.rows = rows;
    this.cols = cols;
    this.threshold = threshold;
    initDigitSum();
    boolean[][] marked = new boolean[rows][cols];
    dfs(marked, 0, 0);
    return cnt;
}

private void dfs(boolean[][] marked, int r, int c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || marked[r][c])
        return;
    marked[r][c] = true;
    if (this.digitSum[r][c] > this.threshold)
        return;
    cnt++;
    for (int[] n : next)
        dfs(marked, r + n[0], c + n[1]);
}

private void initDigitSum() {
    int[] digitSumOne = new int[Math.max(rows, cols)];
    for (int i = 0; i < digitSumOne.length; i++) {
        int n = i;
        while (n > 0) {
            digitSumOne[i] += n % 10;
            n /= 10;
        }
    }
    this.digitSum = new int[rows][cols];
    for (int i = 0; i < this.rows; i++)
        for (int j = 0; j < this.cols; j++)
            this.digitSum[i][j] = digitSumOne[i] + digitSumOne[j];
}

😄总结

通过深度优先搜索算法，我们成功地解决了该问题。我们在搜索的过程中，使用标记数组来避免重复访问，并通过预先计算的数位之和数组来快速判断某个格子是否可达。最终，我们能够在给定的条件下，准确计算出机器人可以到达的格子数量。该算法不仅有效地处理了题目中的限制条件，还能够在合理的时间和空间复杂度内完成任务，是一种实用的解法。

😁热门专栏推荐
想学习vue的可以看看这个

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持