11.机器人的运动范围

本题知识点：数组

题目描述

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

解题思路

回溯法
核心思路：

  1. 从(0,0)开始走，每成功走一步标记当前位置为true,然后从当前位置往四个方向探索，
    返回1 + 4 个方向的探索值之和。
  2. 探索时，判断当前节点是否可达的标准为：
    • 1）当前节点在矩阵内；
    • 2）当前节点未被访问过；
    • 3）当前节点满足limit限制。

代码实现

java 代码

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

    /**
     * 检测每一步是否可达，如果已经进入过该格子，标志位记为true，为进入过，记为false
     * @param threshold k值
     * @param rows 行数m
     * @param cols 列数n
     * @param i 当前格子横（行）坐标
     * @param j 当前格子竖（列）坐标
     * @param flag 格子是否已经进入过标志数组
     * @return
     */
    public int movingStep(int threshold, int rows, int cols, int i, int j, boolean[][] flag) {
        if (i < 0 || j < 0 || i >= rows || j >= cols || flag[i][j]) {
            return 0;
        }
        if (numSumByByte(i) + numSumByByte(j) > threshold) {
            return 0;
        }
        flag[i][j] = true;
        return 1 + movingStep(threshold, rows, cols, i - 1, j, flag)
                + movingStep(threshold, rows, cols, i + 1, j, flag)
                + movingStep(threshold, rows, cols, i, j - 1, flag)
                + movingStep(threshold, rows, cols, i, j + 1, flag);

    }

    /**
     * 计算每个数的个位数上的值之和
     * @param num
     * @return
     */
    private int numSumByByte(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }

    public static void main(String[] args){
         System.out.println(movingCount(18,50,50));
    }

Kotlin 代码

     /**
     * 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
     * @param threshold k值
     * @param rows 行数m
     * @param cols 列数n
     * @return
     */
    fun movingCount(threshold: Int, rows: Int, cols: Int): Int {
        val flag =
            Array(rows) { BooleanArray(cols) }
        return movingStep(threshold, rows, cols, 0, 0, flag)
    }

    /**
     * 检测每一步是否可达，如果已经进入过该格子，标志位记为true，为进入过，记为false
     * @param threshold k值
     * @param rows 行数m
     * @param cols 列数n
     * @param i 当前格子横（行）坐标
     * @param j 当前格子竖（列）坐标
     * @param flag 格子是否已经进入过标志数组
     * @return
     */
    fun movingStep(
        threshold: Int,
        rows: Int,
        cols: Int,
        i: Int,
        j: Int,
        flag: Array<BooleanArray>
    ): Int {
        if (i < 0 || j < 0 || i >= rows || j >= cols || flag[i][j]) {
            return 0
        }
        if (numSumByByte(i) + numSumByByte(j) > threshold) {
            return 0
        }
        flag[i][j] = true
        return (1 + movingStep(threshold, rows, cols, i - 1, j, flag)
                + movingStep(threshold, rows, cols, i + 1, j, flag)
                + movingStep(threshold, rows, cols, i, j - 1, flag)
                + movingStep(threshold, rows, cols, i, j + 1, flag))
    }

    /**
     * 计算每个数的个位数上的值之和
     * @param num
     * @return
     */
    private fun numSumByByte(num: Int): Int {
        var num = num
        var sum = 0
        while (num > 0) {
            sum += num % 10
            num /= 10
        }
        return sum
    }

    /**
     * 入口函数
     */
    fun main(args: Array<String>) {
        println(movingCount(18,50,50))
    }

引用声明

该题目引用自
牛客网