机器人的运动范围(广搜和递推，C++)

剑指 Offer 13. 机器人的运动范围

题目链接

这道题可以简化一下，只剩下从（0,0）开始向下和向右走。
二维图扫描可以考虑用广搜或深搜。
这里给出广搜以及写广搜想到的递推方法。
C++:

class Solution {
public:
   static int get(int x)
    {
        int sum = 0;
        while(x)
        {
            sum +=x%10;
            x = x/10;
        }
        return sum;
    }
    int movingCount(int m, int n, int k) {
        if(!k) return 1;
        queue<pair<int, int>> q;
        int ans = 1;
        vector<vector<bool>> visit(m, vector<bool>(n, false));
        visit[0][0] = true;
        q.push({0, 0});
        int d[][2] = {{0, 1}, {1, 0}};
        while(!q.empty())
        {
            int len = q.size();
            for(int i = 0; i < len; i++)
            {
                auto node = q.front();
                q.pop();
                for(int j = 0; j < 2; j++)
                {
                    int x = node.first + d[j][0];
                    int y = node.second+ d[j][1];
                    if(x >= m || y >= n || visit[x][y] || get(x) + get(y) > k) continue;
                    q.push({x, y});
                    visit[x][y] = true;
                    ans++;
                }
                
            }
        }
        return ans;

    }
};

由广搜可以看出，一个方格是否能到达，取决于他的上一个方格。
递推方法：
C++：

class Solution {
public:
   static int get(int x)
    {
        int sum = 0;
        while(x)
        {
            sum +=x%10;
            x = x/10;
        }
        return sum;
    }
    int movingCount(int m, int n, int k) {
        if(!k) return 1;
        vector<vector<int>> visit(m, vector<int>(n, 0));
        visit[0][0] = 1;
        int ans = 1;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if((i == 0 && j ==0) || get(i) + get(j) > k)
                    continue;
                if(i >= 1) visit[i][j] |= visit[i-1][j];
                if(j >= 1) visit[i][j] |= visit[i][j-1];
                ans+=visit[i][j];
            }
        }
        return ans;

    }
};

如果对你有帮助，请点个赞吧！

本文地址：https://blog.csdn.net/qq_41946404/article/details/110498058