题解 | #机器人的运动范围#

#include <iostream>
#include <string>
#include <vector>
using namespace std;
#include <vector>
class Solution {
public:
    int res = 0;  //能访问的个数
    int dir[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };
    int getSum(int rows, int cols) {   //求位数之和
        int sum = 0;
        while (rows) {
            sum += rows % 10;
            rows /= 10;
        }
        while (cols) {
            sum += cols % 10;
            cols /= 10;
        }
        return sum;
    }
    void dfs(int threshold, int rows, int cols, vector<vector<bool>>& vis, int x, int y) {
        if (getSum(x, y) <= threshold && vis[x][y] == false) {
            res++;
            vis[x][y] = true;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) {  //边界不满足
                continue;
            }
            if (vis[nx][ny] == true) {   //已经访问过
                continue;
            }
            if (getSum(nx, ny) > threshold) {  //大于阈值
                continue;
            }
            dfs(threshold, rows, cols, vis, nx, ny);
        }
    }
    int movingCount(int threshold, int rows, int cols) {
        vector<vector<bool>> vis(rows, vector<bool>(cols, false));
        dfs(threshold, rows, cols, vis, 0, 0);  //从[0][0]开始判断
        return res;
    }
};