机器人的运动范围

记忆点

• 递归
• 从开始

思路

用递归。
目标是从开始，找到所有的可以访问的点，所以理论上矩阵上的每个点最多访问一次。

实现

class Solution {
public:
    int getSum (int x, int y) {
        int s = 0;
        while (x) {
            s += x % 10;
            x /= 10;
        }
        while (y) {
            s += y % 10;
            y /= 10;
        }
        return s;
    }

    int step(int x, int y, int threshold, vector<vector<bool>>& visited) {
        if (x < 0 || x >= visited.size() || y < 0 || y >= visited[x].size()) return 0;
        if (visited[x][y] || getSum(x, y) > threshold) return 0;

        int cnt = 1;
        visited[x][y] = true;
        cnt += step(x+1, y, threshold, visited);
        cnt += step(x-1, y, threshold, visited);
        cnt += step(x, y+1, threshold, visited);
        cnt += step(x, y-1, threshold, visited);
        return cnt;
    }

    int movingCount(int threshold, int rows, int cols) {
        if (threshold < 0 || rows <= 0 || cols <= 0) return 0;

        int cnt = 0;
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        cnt += step(0, 0, threshold, visited);
        return cnt;
    }
};