机器人的运动范围

本贴最后更新于 2467 天前,其中的信息可能已经时过境迁

题目描述

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

解题思路

回溯法。利用标志位记录已经走过的位置,不过这里不需要对其去标志处理,任何一种方法到达都可以。然后记录在 ret 矩阵中,或者计算标志位中标志的个数。

代码

public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        int[] ret = new int[1];
        boolean[][] label = new boolean[rows][cols];
        canThis(threshold, rows, cols, 0, 0, label, ret);
        return ret[0];
    }
    
    private void canThis(int threshold, int rows, int cols, int row, int col, boolean[][] label, int[] ret) {
        if (row < 0 || col < 0 || row >= rows || col >= cols || label[row][col] == true)
            return;
        int k = 0;
        int tcol = col;
        int trow = row;
        while (trow != 0) {
            k += trow % 10;
            trow /= 10;
        }
        while (tcol != 0) {
            k += tcol % 10;
            tcol /= 10;
        }
        if (k <= threshold) {
            ret[0]++;
            label[row][col] = true;
            canThis(threshold, rows, cols, row+1, col, label, ret);
            canThis(threshold, rows, cols, row-1, col, label, ret);
            canThis(threshold, rows, cols, row, col+1, label, ret);
            canThis(threshold, rows, cols, row, col-1, label, ret);
        } else
            return;
    }
}

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...