机器人的运动范围

机器人的运动范围

题目链接

牛客网

题目描述

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

数据范围: 机器人的运动范围机器人的运动范围

进阶:空间复杂度 机器人的运动范围 ,时间复杂度 机器人的运动范围

实例1

输入:

1,2,3

返回值:

3

实例2

输入:

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]等等是无法到达的

题目分析

题中说了,机器人是可以沿着上下左右四个方向走的。但你想一下,任何一个格子你从任何一个方向进来,那么他只能往其他3个方向走,因为如果在往回走就重复了。但实际上我们只要沿着两个方向走就可以了,一个是右边,一个是下边

package com.huang.algorithms;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author hxc
 * @Date 2022/1/10
 * 机器人运动范围
 */

public class RobotMotion {
    public static void main(String[] args) {

        int i = movingCount(10, 1, 100);
        System.out.println(i);

    }

    /**
     * 地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。
     * 一个机器人从坐标 [0,0] 的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,
     * 但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。
     * 例如,当 threshold 为 18 时,机器人能够进入方格   [35,37] ,因为 3+5+3+7 = 18。
     * 但是,它不能进入方格 [35,38] ,因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子?
     *
     * @param threshold
     * @param rows
     * @param cols
     * @return
     */
    public static int movingCount(int threshold, int rows, int cols) {
        boolean[][] flag = new boolean[rows][cols];
        return dfs(0, 0, rows, cols, threshold, flag);
    }

    //深度优先
    private static int dfs(int i, int j, int rows, int cols, int threshold, boolean[][] flag) {
        /**
         * i >= rows || j >= cols是边界条件的判断,threshold < sum(i, j)判断当前格子坐标是否
         满足条件,visited[i][j]判断这个格子是否被访问过
         */
        if (i >= rows || j >= cols || threshold < sum(i, j) || flag[i][j]) {
            return 0;
        }
        flag[i][j] = true;
        //向下或者向右查找
        return 1 + dfs(i + 1, j, rows, cols, threshold, flag) + dfs(i, j + 1, rows, cols, threshold, flag);
    }

    //算坐标索引的和
    private static int sum(int i, int j) {
        int sum = 0;
        while (i != 0) {
            //得个位数
            sum += i % 10;
            //变个位数
            i = i / 10;
        }
        while (j != 0) {
            sum += j % 10;
            j = j / 10;
        }
        return sum;
    }

}
上一篇:opencv学习笔记之图像操作


下一篇:The Φ Accrual Failure Detector机制学习总结