题解 | #机器人的运动范围# 11-3 01

class Solution { public: vector<vector> visited; int cnt = 0; int calNums(int i, int j) { int ret = 0; while(i) { ret += i % 10; i /= 10; } while(j) { ret += j % 10; j /= 10; } return ret; }

void dfs(int x, int y, int rows, int cols, int threshold) {
    // 检查下标
    if(x < 0 || x >= rows || y < 0 || y >= cols) {
        return;
    }
    // 是否被访问过
    if(visited[x][y]) {
        return;
    }
    // 是否满足条件返回
    if (calNums(x, y) > threshold) {
        return;
    }
    visited[x][y] = true;
    cnt++;
    // dfs
    dfs(x + 1, y, rows, cols, threshold);
    dfs(x - 1, y, rows, cols, threshold);        
    dfs(x, y + 1, rows, cols, threshold);        
    dfs(x, y - 1, rows, cols, threshold);        
}    

int movingCount(int threshold, int rows, int cols) {
    visited = vector<vector<bool>>(rows, vector<bool>(cols, false));
     dfs(0, 0,rows, cols, threshold);
    /*
    for(int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (calNums(i, j ) <= threshold) {
                dfs(i, j,rows, cols, threshold);
            }
        }
    }
    */
    return cnt;
}

};