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

#include <vector>
class Solution {
public:
    int num = 0;
    int get_value(int val)
    {
        int res = 0;
        while (val) {
            res += val%10;
            val /=10;
        }
        return res;
    }
    
    void dfs(int threshold, vector<vector<int>>& mat, vector<vector<bool>>& board, int i, int j)
    {
        // 到达边界、走过的、格子数值大于阈值则停止
        if(i < 0 || i > mat.size() - 1|| j < 0 || j > mat[0].size() -1  || board[i][j] || get_value(i) + get_value(j) > threshold)
            return;
        board[i][j] = true; // 若格子可行，则标记为true
        num += 1;
        
        // 上下左右遍历找可行格子
        dfs(threshold, mat, board, i - 1, j);
        dfs(threshold, mat, board, i + 1, j);
        dfs(threshold, mat, board, i, j - 1);
        dfs(threshold, mat, board, i, j + 1);

        // 添加下面会导致失败。跟JZ12相比，其考虑的是一片范围，而非单一路径。范围表示的是，走过就是走过了，未来的上下左右遍历，不再考虑走过的。
        // board[i][j] = false;
        // num -= 1;
        return;
    }
    int movingCount(int threshold, int rows, int cols) {
        
        // 记录走过的格子
        vector<vector<bool>> board(rows,vector<bool>(cols, false));
        //初始化行列矩阵
        vector<vector<int>> mat(rows,vector<int>(cols, 0));
        dfs(threshold, mat, board, 0, 0);
        return num;
    }
};