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

欢迎关注我的博客：https://www.cnblogs.com/Cloud-king/

#include <cstring>
#include <unistd.h>
class Solution {
public:
    int swsum(int x){
        int ans=0;
        while (x>=1) {
            ans+=x%10;
            x/=10;
        }
        return ans;
    }
    int vis[105][105]={0};
    int nex[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
    int ans=1;
    void dfs(int th,int x,int y,int n,int m){
        for(int i=0;i<4;i++){
            int dx=x+nex[i][0];
            int dy=y+nex[i][1];
            int tmp=swsum(dx)+swsum(dy);  
            //cout << dx << " " << dy << endl;  
            if(dx<n&&dx>=0&&dy>=0&&dy<m&&tmp<=th&&vis[dx][dy]==0){     
                vis[dx][dy]=1;
                ans++;               
                //cout << dx << " " << dy << " " << ans << endl;
                dfs(th,dx,dy,n,m);
                //vis[dx][dy]=0;  //重复的格子也能走；
            }
        }
    }
    int movingCount(int threshold, int rows, int cols) {
        memset(vis, 0, sizeof(vis));
        vis[0][0]=1;
        dfs(threshold,0,0,rows,cols);
        return ans;
    }
};

不需要回溯，只需要一个变量记录那些搜索过程中遇到的能到的格子，因为题目只是记录能到达的格子数量而不是一条可行的不能回头的路径。感觉更适合bfs去做。

#include <cstring>
#include <queue>
#include <unistd.h>
#include <utility>
class Solution {
public:
    int swsum(int x){
        int ans=0;
        while (x>=1) {
            ans+=x%10;
            x/=10;
        }
        return ans;
    }
    int vis[105][105]={0};
    int nex[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
    int ans=0;
    void bfs(int th,int n,int m){
        queue<pair<int,int>> q;
        q.push({0,0});
        while (!q.empty()) {
            pair<int, int> tmp=q.front();
            q.pop();    //不要忘记pop
            ans++;
            for(int i=0;i<4;i++){
                int dx=tmp.first+nex[i][0];
                int dy=tmp.second+nex[i][1];
                int su=swsum(dx)+swsum(dy);
                if(dx>=0&&dx<n&&dy>=0&&dy<m&&su<=th&&vis[dx][dy]==0){
                    q.push({dx,dy});
                    vis[dx][dy]=1;
                }
            }
        }
    }
    int movingCount(int threshold, int rows, int cols) {
        memset(vis, 0, sizeof(vis));
        vis[0][0]=1;
        bfs(threshold, rows, cols);
        return ans;
    }
};