机器人的运动范围(广搜和递推,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. 机器人的运动范围
题目链接
这道题可以简化一下,只剩下从(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
上一篇: unittestreport 实用功能之钉钉群推送测试结果
下一篇: 智能硬件产品开发分享