剑指Offer：机器人的运动范围

CoderBear 发布于2019-08-15 15:46 / 2994人阅读

摘要：例如，当为时，机器人能够进入方格，因为。请问该机器人能够达到多少个格子分析这题和上题剑指矩阵中的路径属于同一类型的题目。

题目

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

分析

这题和上题剑指Offer：矩阵中的路径属于同一类型的题目。所以大致思路相同，只需要将判断条件变成判断他是否能够达到相应的格子（即判断即将进入个格子行坐标和列坐标的数位之和是否大于k）而且其实坐标已经确定了，实现相对简单

public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        if (threshold < 0 || rows <= 0 || cols <= 0)
            return 0;
        boolean[] visited = new boolean[rows*cols];
        
        return moveCount(threshold, rows, cols, 0, 0, visited);
    }
    
    public int moveCount(int threshold, int rows, int cols, int row, int col, boolean[] visited) {
        int count = 0;
        if (isOK(threshold, row, col) && row >= 0 && col >= 0 && row < rows && col < cols && !visited[cols*row+col]) {
            visited[row*cols + col] = true;
            count = 1 + moveCount(threshold, rows, cols, row-1, col, visited) + 
                        moveCount(threshold, rows, cols, row, col-1, visited) + 
                        moveCount(threshold, rows, cols, row+1, col, visited) + 
                        moveCount(threshold, rows, cols, row, col+1, visited);
        }
        return count;
    }
    
    // 判断即将进入个格子行坐标和列坐标的数位之和是否大于k
    public boolean isOK(int threshold, int row, int col){
        int sum = 0;
        while (row != 0){
            sum += (row%10);
            row /= 10;
        }
        while (col != 0){
            sum += (col%10);
            col /= 10;
        }
        if (sum > threshold)
            return false;
        else
            return true;
    }
}

GPU云服务器云服务器剑指粒子的运动js 会话时间保持的范围人工智能的范围

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69255.html

LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
剑指offer之基础知识数组

摘要：附上和实现二维数组中的查找题目描述在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。为了实习的准备，开始刷题来巩固基础算法和数据结构，大神轻喷。 1.数组中重复的数字题目描述：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有...

zhou_you 2019-08-22 13:49 评论0 收藏0
剑指Offer【3(2)】：不修改数组找出重复的数字

摘要：题目在一个长度为的数组里面的所有数字都在的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为的数组，那么对应的输出是重复的数字或者。题目在一个长度为n+1的数组里面的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为9的数组{2,3...

SoapEye 2019-08-19 11:37 评论0 收藏0
剑指Offer【3】：数组中重复的数字

摘要：题目描述在一个长度为的数组里的所有数字都在到的范围内。请找出数组中任意一个重复的数字。例如，如果输入长度为的数组，那么对应的输出是第一个重复的数字。判断数组是否为空参考剑指题目描述在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,...

vpants 2019-08-19 11:37 评论0 收藏0
剑指offer系列——剑指 Offer 24. 反转链表（C语言）

摘要：假设反转对象节点为，反转指向的结点为，反转后指向的结点为首结点。当然也可以根据栈先进后出的特点，使用栈反转链表。 ⭐️前面的话⭐️ 大家好！博主开辟了一个新的专栏—...

weakish 2021-09-03 10:29 评论0 收藏0