【剑指 offer】机器人的运动范围（BFS）

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;
    }
};