JZ13 机器人的运动范围

发表于 分类于 本文字数： 518 阅读时长 ≈ 2 分钟

JZ13 机器人的运动范围

描述

地上有一个 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 。

数据范围： $0≤threshold≤15 $ ，$1≤rows,cols≤100 $

进阶：空间复杂度 $O(nm) $ ，时间复杂度 $O(nm) $

示例1

1
2
输入：1,2,3
返回值：3

示例2

1
2
输入：0,1,3
返回值：1

示例3

1
2
3
4
输入：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]等等是无法到达的

示例4

1
2
输入：5,10,10
返回值：21

题解

我们用数对$x,y$来表示机器人当前的坐标，如果从左上角开始移动，那么我们只需要只允许机器人向右和下移动即可。

做出移动，就是让$x或y$变大1，然后开始判断，判断$x和y$的每一位数字加起来是否比$threshold$大，若是的话就给答案+1，若不是就不加，然后回溯$x和y$

那么边界条件是什么？当$x和y$走出边界限制或已被访问过，使用布尔数组$visited$追踪。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
  public:
    int movingCount(int threshold, int rows, int cols) {
        row = rows;
        col = cols;
        ts = threshold;
        visited = vector<vector<bool>>(row, vector<bool>(col, false));
        moving(0, 0);
        return ans;
    }
  private:
    int row;
    int col;
    int ts;
    int ans = 0;
    vector<vector<bool>> visited;

    void moving(int x, int y) {
        if (x < 0 || x >= row || y < 0 || y >= col || visited[x][y]) return;

        int nums = 0, tx = x, ty = y;
        while (tx > 0) {
            nums += tx % 10;
            tx /= 10;
        }
        while (ty > 0) {
            nums += ty % 10;
            ty /= 10;
        }
        if (nums > ts) return;

        visited[x][y] = true;
        ans += 1;

        moving(x + 1, y);
        moving(x, y + 1);
    }
};