笔者今天在做力扣每日一题时,遇到一道经典的BFS题目:
面试题13. 机器人的运动范围
地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?
示例 1: 输入:m = 2, n = 3, k = 1
输出:3
示例 1:
输入:m = 3, n = 1, k = 0
输出:1
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
采用BFS的方法可以很轻松的解决这道题。这里我采用的C++来实现的BFS,在用C++实现BFS时,需要注意的是两个关键的数据结构,一个是队列,用以实现广度搜索,一个是map,用以判断已经“走”过的节点。同时这道题中,还应用了一个map用以计算已经计算过的值,是典型的空间换时间的思路(不过比较搞笑的是,最终结果显示的是空间击败了100%,但时间只击败了5.67%)。
以下是我的代码,还有优化的空间,但这个代码却是可以很好的反映出BFS的思路
class Solution {
public:
map<int, int>valuestore;
int getvalue(int x)
{
if (x >= 0 && x <= 9)
return x;
if (valuestore.find(x) != valuestore.end())
return valuestore[x];
int ret = 0;
while (x)
{
ret += x % 10;
x = x / 10;
}
valuestore[x] = ret;
return ret;
}
int movingCount(int m, int n, int k) {
if (k == 0)
return 1;
queue<pair<int, int>>bfs;
map<pair<int, int>, int>store;
bfs.push(pair<int, int>{0, 0});
int step = 0;
while (!bfs.empty())
{
pair<int, int>tmp = bfs.front();
bfs.pop();
store[tmp] = 1;
step++;
int x = getvalue(tmp.first);
int y = getvalue(tmp.second);
if (tmp.first + 1 < m && (getvalue(tmp.first + 1) + y <= k))
{
pair<int, int>move{ tmp.first + 1, tmp.second };
if (store[move] != 1)
{
bfs.push(move);
store[move] = 1;
}
}
if (tmp.first - 1 >= 0 && (getvalue(tmp.first - 1) + y <= k))
{
pair<int, int>move{ tmp.first - 1, tmp.second };
if (store[move] != 1)
{
bfs.push(move);
store[move] = 1;
}
}
if (tmp.second + 1 < n && (x + getvalue(tmp.second + 1) <= k))
{
pair<int, int>move{ tmp.first, tmp.second + 1 };
if (store[move] != 1)
{
bfs.push(move);
store[move] = 1;
}
}
if (tmp.second - 1 >= 0 && (x + getvalue(tmp.second - 1) <= k))
{
pair<int, int>move{ tmp.first, tmp.second - 1 };
if (store[move] != 1)
{
bfs.push(move);
store[move] = 1;
}
}
}
return step;
}
};