专栏首页Java小白成长之路剑指offer第11题:机器人运动范围

剑指offer第11题:机器人运动范围

机器人运动范围

剑指Offer 13:机器人的运动范围 【中等】”

题目描述

方法:

此方法我们可以直接按照题目中的要求,将所有的方格全都访问一遍,由于所有的格子需要满足一个条件,连续性和单元格的坐标和小于n即可。

我们使用==递归==的方式进行完成。首先我们自己来初始化一个boolen[][]矩阵,用来标记每一个方格是否可达。如果当前方格(i,j)可达,我们继续向下和向右遍历,如果当前方格(i,j)不可达,那么我们则不再需要继续向后递归。

当我们完成整个方格的标记之后,我们遍历存放可达的boolean矩阵,然后进行统计可达的个数就好了~

代码实现

class Solution {

    public int movingCount(int m, int n, int k) {
        boolean[][] flag = new boolean[m][n];//记录访问了哪些格子
        extend(flag , 0 , 0 , m , n , k);
        int res = 0;
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < n ; j++){
                if(!flag[i][j]) continue;//如果当前的格子已经遍历过了,则不再进行遍历了
                res++;
            }
        }
        return res;
    }
    private void extend (boolean[][] flag , int row , int col , int m , int n , int k){
        //判断当前格子是否已经超出范围并且确保没有被访问过
        if(row < 0 || row >= m || col < 0 || col >= n || flag[row][col]) return;

        int sum = 0 ;
        int i = row , j = col ;
        while(row > 0 || col > 0){
            sum += row%10 + col%10;
            row /= 10;
            col /= 10;
        }
        if(sum > k) return; //判断是否可达
        flag[i][j] = true;

        //我们规定机器人都是从左上角开始移动的,所以我们只需要让机器人向右或者向下即可
        extend(flag , i+1 , j , m , n , k);//向下
        extend(flag , i , j+1 , m , n , k);//向右
    }
}

【思考】

此题的解题思路是比较明显的,就是递归思想,在很多题解里面所说的DFS其实本质上也是一种递归的表现形式,首先弄清楚何时递归,何时不可递归,以及每次递归时我们需要的处理即可。大致可以从这道题目中略见一二。

本文分享自微信公众号 - Java小白成长之路(Java_xiaobai),作者:鹏程万里

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer第10题:矩阵中的路径

    根据题目要求,需要我们从一个已知矩阵中找到一个可以挨个形成给定字符串的路径。如果有这条路径的话,我们需要返回true,如果没有的话,我们返回false,并且相同...

    鹏-程-万-里
  • 回溯:系列经典题目

    对于回溯算法,一开始接触感觉还是挺难的,随着刷到的题目的数量增多,慢慢也可以总结出来相应的套路出来。大家一起来看看下面的伪代码

    鹏-程-万-里
  • 剑指offer第5题:重建二叉树

    这道题要求我们根据中序遍历和前序遍历构建一颗二叉树。在前序遍历中,遍历顺序为根节点-->左节点-->右节点,中序遍历顺序为左节点-->根节点-->右节点,所以我...

    鹏-程-万-里
  • 策略模式(Strategy)

    - 1.Strategy:策略接口,用来约束一系列具体的策略算法。Context使用这个接口来调用具体的策略,实现定义的策略。

    qubianzhong
  • Codeforces Round #521 (Div. 3) D. Cutting Out(二分)

    题目链接:http://codeforces.com/contest/1077/problem/D

    Ch_Zaqdt
  • BZOJ 4289: PA2012 Tax(最短路)

    Description 给出一个N个点M条边的无向图,经过一个点的代价是进入和离开这个点的两条边的边权的较大值,求从起点1到点N的最小代价。起点的代价是离开起...

    attack
  • HDU 1863 畅通工程

    一道很朴素的最小生成树,不过通过此题知道了,当n已经决定的情况下,若n个点无法构成最小生成树的话,最终得到ans无法得到精确的值,他会将无穷大的路径加入。 #i...

    用户1624346
  • Python3 基础学习之数值进制转换

        这个函数在上篇里表示强转,并没有输入n这个参数。当n不输入的时候默认是n=10。

    ZY_FlyWay
  • 2017.5.26暴力赛解题报告

    预计分数:T1:40AC+60TLE      T2:40AC+60TLE        T3:10AC+90TLE      总分=90 实际分数:T1:10...

    attack
  • 1048 石子归并

    1048 石子归并 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 有n堆石子...

    attack

扫码关注云+社区

领取腾讯云代金券