题目描述
地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。
一个机器人从坐标 (0,0) 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
请问该机器人能够达到多少个格子？
注意:
0<=m<=500<=n<=500<=k<=100
样例1
输入：k=7, m=4, n=5 输出：20
样例2
输入：k=18, m=40, n=40 输出：1484 解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。 但是，它不能进入方格（35,38），因为3+5+3+8 = 19。
方法一：BFS O(n)
这道题我们直接用宽搜来做，从 (0,0) 开始往外扩展，也是一道基本的模板题。具体思路如下，我们拿 k=3,m=4,n=5 这个情况来举例：
第一步： 如果行数或列数为 0 的话直接返回 0 ，但是这里不为 0 ，所以继续执行下面的操作。
第二步： 这道题我们可以从坐标 (0,0) 开始进行 bfs ，用一个队列来保存后续满足要求的坐标，最开始先推入 (0,0) ，因为它的 x+y<k 满足要求。
第三步： 开始 bfs ，将队列的队首元素推出，得到 (0,0) ，然后去遍历它的上下左右四个方向上的格子，如果满足要求则加入队列。bfs 其实就像从一个点开始，一层一层的往外进行遍历，如果遇到满足要求的点就加入到数组中去。
第四步： 只要队列不为空，就一直往外遍历，这里就直接放图啦。
第五步： 由于 k=3 ，故只要 x+y>k 的地方都不能到达，所以最后会返回答案 res=10 。
class Solution { public: //计算数的每位之和 int cal(int x) { int ans = 0; for (; x; x /= 10) ans += x % 10; return ans; } int dx[4] = { 0,-1,0,1 }, dy[4] = { 1,0,-1,0 }; int movingCount(int threshold, int rows, int cols) { if (!rows || !cols) return 0; queue<pair<int, int>> q; vector<vector<int>> table(rows, vector<int>(cols, 0)); //用来判断是否当前位置已经遍历过 //将(0,0)先push进去 table[0][0] = 1; q.push({ 0,0 }); int ans = 0; //开始bfs while (!q.empty()) { auto it = q.front(); q.pop(); ans++; for (int i = 0; i < 4; i++) { int mr = it.first + dx[i], mc = it.second + dy[i]; //判断当前 if (mr < 0 || mr >= rows || mc < 0 || mc >= cols || table[mr][mc]) continue; if (cal(mr) + cal(mc) > threshold) continue; table[mr][mc] = 1; //记录当前位置已经走过 q.push({ mr,mc }); } } return ans; } };
欢迎大家在评论区交流~
