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

class Solution {
public:
    int nex[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
    bool vis[100][100];
    int r;
    int c;
    int getsum(int x){
        int ans = 0;
        while(x){
            ans += x%10;
            x /= 10;
        }
        return ans;
    }
    int ans;
    void bfs(int x,int y,int k){
        cout << ans << endl;                                                                                               
        ans++;
        for(int i=0; i<4; i++){
            int xx = x + nex[i][0];
            int yy = y + nex[i][1];
            if(xx>=0 && yy>=0 && xx<r && yy<c && !vis[xx][yy] && getsum(xx)+getsum(yy)<=k){
                vis[xx][yy] = 1;
                bfs(xx,yy,k);  
                //不能ans += bfs(xx,yy,k) 一条路径多次累加
                //不能bfs(xx,yy,k，ans+1) 这种只会取最长的那条路径的
                //不用vis归0 每个点只要求过一次即可
            }
        }
    }
    int movingCount(int threshold, int rows, int cols) {
        for(int i=0; i<rows; i++)
            for(int j=0; j<cols; j++)
                vis[i][j] = 0;
        vis[0][0] = 1;
        r = rows;
        c = cols;
        ans = 0;
        bfs(0,0,threshold);
        return ans;
    }
};