Skip to content

机器人的移动范围

机器人的移动范围

题目描述

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

解法

从坐标(0, 0) 开始移动,当它准备进入坐标(i, j),判断是否能进入,如果能,再判断它能否进入 4 个相邻的格子 (i-1, j), (i+1, j), (i, j-1), (i, j+1)。

/**
 * @author bingo
 * @since 2018/11/20
 */

public class Solution {
    /**
     * 计算能到达的格子数
     * @param threshold 限定的数字
     * @param rows 行数
     * @param cols 列数
     * @return 格子数
     */
    public int movingCount(int threshold, int rows, int cols) {
        if (threshold < 0 || rows < 1 || cols < 1) {
            return 0;
        }
        boolean[] visited = new boolean[rows * cols];
        return getCount(threshold, 0, 0, rows, cols, visited);
    }

    private int getCount(int threshold, int i, int j, int rows, int cols, boolean[] visited) {
        if (check(threshold, i, j, rows, cols, visited)) {
            visited[i * cols + j] = true;
            return 1
                    + getCount(threshold, i - 1, j, rows, cols, visited)
                    + getCount(threshold, i + 1, j, rows, cols, visited)
                    + getCount(threshold, i, j - 1, rows, cols, visited)
                    + getCount(threshold, i, j + 1, rows, cols, visited);
        }
        return 0;
    }

    private boolean check(int threshold, int i, int j, int rows, int cols, boolean[] visited) {
        return i >= 0
                && i < rows
                && j >= 0
                && j < cols
                && !visited[i * cols + j]
                && getDigitSum(i) + getDigitSum(j) <= threshold;
    }

    private int getDigitSum(int i) {
        int res = 0;
        while (i > 0) {
            res += i % 10;
            i /= 10;
        }
        return res;
    }
}

测试用例

  1. 功能测试(方格为多行多列;k 为正数);
  2. 边界值测试(方格只有一行或者一列;k = 0);
  3. 特殊输入测试(k < 0)。


回到顶部