欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

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

程序员文章站 2022-03-04 23:38:34
剑指 Offer 13. 机器人的运动范围题目链接这道题可以简化一下,只剩下从(0,0)开始向下和向右走。二维图扫描可以考虑用广搜或深搜。这里给出广搜以及由广搜的思想引起的另一种方法。C++:class Solution {public: static int get(int x) { int sum = 0; while(x) { sum +=x%10; x = x/10;...

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

题目链接
机器人的运动范围(广搜和递推,C++)
这道题可以简化一下,只剩下从(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