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))
}

引用声明

该题目引用自
牛客网