1、题目描述
地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。
一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
请问该机器人能够达到多少个格子？
样例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。
注意:
0<=m<=50
0<=n<=50
0<=k<=100
2、问题描述：
- 矩形，行列值为坐标，坐标的各个位的数子和小于k可以进入，求有多少个。
3、问题关键：
- 典型的BFS题目。
-
可以从（0，0）开始，每次都往上下左右四个方向扩展新的结点。
-
满足的条件：1。之前没有遍历过；2。没有走出边界；3.横纵坐标之和小于k。
-
建立一个队列用于扩展要遍历的点，如果当前点满足条件就将其上下左右合法的结点加入队列。
-
建立一个状态空间矩阵，保存每个结点是否被遍历过。vector<vector<bool>> st(rows, vector<bool>(cols));
4、C++代码：
class Solution {
public:
int getSum(pair<int, int> q) {//这个是一个求每个坐标的和的函数。
int s = 0;
while(q.first) {//依次取出横坐标的每一位，累加。
s += q.first % 10;
q.first /= 10;
}
while(q.second) {//依次取出纵坐标的每一位，累加。
s += q.second % 10;
q.second /= 10;
}
return s;
}
int movingCount(int threshold, int rows, int cols)
{
if(!rows || !cols) return 0;
queue<pair<int, int>> q;//遍历队列。
vector<vector<bool>> st(rows, vector<bool>(cols));//状态矩阵，记录是否遍历过。
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//坐标移动方向。
int res = 0;
q.push({0, 0});
while(q.size()) {
auto t = q.front();
q.pop();
if (st[t.first][t.second] || getSum(t) > threshold) continue;//如果结点不满足，直接进行下一次遍历。
res ++;
st[t.first][t.second] = true;／遍历完了一定要做一下标记，我两次都忘记了。
for (int i = 0; i < 4; i ++) {
int x = t.first + dx[i], y = t.second + dy[i];//如果它周围的结点在合法的区域，那么加入队列。
if (x >= 0 && x < rows && y >= 0 && y < cols)
q.push({x, y});
}
}
return res;
}
};
