C++刷剑指offer(面试题13. 机器人的运动范围)【广度优先搜索】【pair make_pair】

糖逗

题目描述：

地上有一个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
提示：

1 <= n,m <= 100
0 <= k <= 20

#include <iostream>
#include <queue>

using namespace std;


int sum(int n) {
    int s = 0;
    while (n > 0){
        s += n%10;
        n /= 10;
    }

    return s;
}



void bfs(int m, int n, int k, int& count, vector<vector<bool> >& visit, queue<pair<int, int> >& que) {
        pair<int, int> p(0, 0);
        while (!que.empty()) {
            p = que.front();
            que.pop();
        
            count++;
            if (p.first + 1 >= 0 && p.first + 1 < m && p.second >= 0 && p.second < n &&
                sum(p.first + 1) + sum(p.second) <= k && !visit[p.first + 1][p.second]) {
                que.push({p.first + 1, p.second});
                visit[p.first + 1][p.second] = true;
            }
        
            if (p.first >= 0 && p.first < m && p.second + 1 >= 0 && p.second + 1 < n &&
                sum(p.first) + sum(p.second + 1) <= k && !visit[p.first][p.second + 1]) {
                que.push({p.first, p.second + 1});
                visit[p.first][p.second + 1] = true;
            }
        }
}


int movingCount(int m, int n, int k) {
    vector<vector<bool> > visit(m, vector<bool>(n, false));
    int c = 0;
    queue<pair<int, int> > que;

    pair<int, int> p = make_pair(0, 0);
    que.push(p);

    visit[p.first][p.second] = true;
    bfs(m, n, k, c, visit, que);
    return c;
}



int main(void){
        int m, n, k;
        cin >> m;
        cin.clear();
        cin >> n;
        cin.clear();
        cin >> k;
        cin.clear();
        int res = movingCount(m, n, k);
        cout << res << endl;
        return 0;
        
}

注意事项：
1.参考链接：https://leetcode-cn.com/problems ... -by-luo-jing-yu-yu/
2.pair make_pair 参考链接：https://blog.csdn.net/weixin_42825576/article/details/81571419
3.这里int&count 里边有&引用，可以改变count值。

糖逗

这道题做的不好，还需要再做一遍。