机器人的运动范围

题目描述

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

解答

dfs遍历即可

/**
 * 用来判断是否访问过
 */
Set<String> set = new HashSet<>();
int X, Y, max;
int count = 0;

public int movingCount(int threshold, int rows, int cols) {

    X = rows;
    Y = cols;
    max = threshold;

    dfs(0, 0);
    return count;
}

private void dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= X || y >= Y) {
        return;
    }
    String id = x + "," + y;
    if (set.contains(id)) {
        return;
    } else {
        set.add(id);
    }
    char[] xs = String.valueOf(x).toCharArray();
    char[] ys = String.valueOf(y).toCharArray();
    int xc = 0, yc = 0;
    for (char c : xs) {
        xc += (c - '0');
    }
    for (char c : ys) {
        yc += (c - '0');
    }
    if (xc + yc > max) {
        return;
    }
    count++;
    dfs(x - 1, y);
    dfs(x + 1, y);
    dfs(x, y - 1);
    dfs(x, y + 1);
}

官方解答

链接：https://www.nowcoder.com/questionTerminal/6e5207314b5241fb83f2329e89fdecc8?answerType=1&f=discussion
来源：牛客网

方法一：DFS遍历

根据题目描述，我们可以模拟题目，我们假设一个5x5矩阵，阈值sho=3，如果我们用DFS的话，就相当于“不撞南墙不回头”，我在下面画了一个图，

最开始，我们在(0,0)的位置，我们假设按照{右，下，左，上}的方向去试探。所以我们走的顺序应该是按照图中的下标走的。
当走到4的时候，发现不能往继续往右边走，并且4个方向都走不通了，那就回溯到3,发现可以走到5，接着就站在5的视角，发现可以走6，就一直按照这个想法。

本题的递归函数就是：首先站在(0,0)的视角，先往右试探，发现可以走，就以下一个为视角，继续做相同的事情。
递归函数模板为：

dfs(){

    // 第一步，检查下标

    // 第二步：检查是否被访问过，或者是否满足当前匹配条件

    // 第三步：检查是否满足返回结果条件

    // 第四步：都没有返回，说明应该进行下一步递归
    // 标记
    dfs(下一次)
    // 回溯
}  
int main() {
    dfs(0, 0);
}

按照模板改写代码：

class Solution {

public:
    using V = vector<int>;
    using VV = vector<V>;    
    int dir[5] = {-1, 0, 1, 0, -1};

    int check(int n) {
        int sum = 0;

        while (n) {
            sum += (n % 10);
            n /= 10;
        }

        return sum;
    }

    void dfs(int x, int y, int sho, int r, int c, int &ret, VV &mark) {
        // 检查下标 和 是否访问
        if (x < 0 || x >= r || y < 0 || y >= c || mark[x][y] == 1) {
            return;
        }
        // 检查当前坐标是否满足条件
        if (check(x) + check(y) > sho) {
            return;
        }
        // 代码走到这里，说明当前坐标符合条件
        mark[x][y] = 1;
        ret += 1;

        for (int i = 0; i < 4; ++i) {
            dfs(x + dir[i], y + dir[i + 1], sho, r, c, ret, mark);
        }



    } 
    int movingCount(int sho, int rows, int cols)
    {
        if (sho <= 0) {
            return 0;
        }

        VV mark(rows, V(cols, -1));
        int ret = 0;
        dfs(0, 0, sho, rows, cols, ret, mark);
        return ret;
    }
};

时间复杂度：O(mn)， m,n为矩阵大小，每个元素最多访问过一次
空间复杂度：O(mn)

方法二：BFS遍历

当前图的遍历算法还有bBFS，所以也可以用BFS做。方法一实例的图，用BFS就是如下这样：

代码如下：

class Solution {
public:
    using pii = pair<int,int>;
    int dir[5] = {-1, 0, 1, 0, -1};
    int check(int n) {
        int sum = 0;

        while (n) {
            sum += (n % 10);
            n /= 10;
        }

        return sum;
    }
    int movingCount(int sho, int rows, int cols)
    {
        if (sho <= 0) {
            return 0;
        }

        int ret = 0;
        int mark[rows][cols];
        memset(mark, -1, sizeof(mark));
        queue<pii> q;
        q.push({0, 0});
        mark[0][0] = 1;


        while (!q.empty()) {
            auto node = q.front();
            q.pop();
            // 每次保证进队列的都是满足条件的坐标
            ++ret;

            for (int i = 0; i < 4; ++i) {
                int x = node.first + dir[i];
                int y = node.second + dir[i + 1];

                if (x >= 0 && x < rows && y >= 0 && y < cols && mark[x][y] == -1) {
                    if (check(x) + check(y) <= sho) {
                        q.push({x, y});
                        mark[x][y] = 1;
                    }
                }
            }
        }

        return ret;
    }
};

时间复杂度：O(mn)， m,n为矩阵大小，每个元素最多访问过一次
空间复杂度：O(mn)