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

糖逗

题目描述：

1. 
   
2. 地上有一个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。请问该机器人能够到达多少个格子？
   
3. 
   
4. 
   
5. 
   
6. 示例 1：
   
7. 
   
8. 输入：m = 2, n = 3, k = 1
   
9. 输出：3
   
10. 示例 1：
    
11. 
    
12. 输入：m = 3, n = 1, k = 0
    
13. 输出：1
    
14. 提示：
    
15. 
    
16. 1 <= n,m <= 100
    
17. 0 <= k <= 20

复制代码

1. #include <iostream>
   
2. #include <queue>
   
3. 
   
4. using namespace std;
   
5. 
   
6. 
   
7. int sum(int n) {
   
8.     int s = 0;
   
9.     while (n > 0){
   
10.         s += n%10;
    
11.         n /= 10;
    
12.     }
    
13. 
    
14.     return s;
    
15. }
    
16. 
    
17. 
    
18. 
    
19. void bfs(int m, int n, int k, int& count, vector<vector<bool> >& visit, queue<pair<int, int> >& que) {
    
20.         pair<int, int> p(0, 0);
    
21.         while (!que.empty()) {
    
22.             p = que.front();
    
23.             que.pop();
    
24.        
    
25.             count++;
    
26.             if (p.first + 1 >= 0 && p.first + 1 < m && p.second >= 0 && p.second < n &&
    
27.                 sum(p.first + 1) + sum(p.second) <= k && !visit[p.first + 1][p.second]) {
    
28.                 que.push({p.first + 1, p.second});
    
29.                 visit[p.first + 1][p.second] = true;
    
30.             }
    
31.        
    
32.             if (p.first >= 0 && p.first < m && p.second + 1 >= 0 && p.second + 1 < n &&
    
33.                 sum(p.first) + sum(p.second + 1) <= k && !visit[p.first][p.second + 1]) {
    
34.                 que.push({p.first, p.second + 1});
    
35.                 visit[p.first][p.second + 1] = true;
    
36.             }
    
37.         }
    
38. }
    
39. 
    
40. 
    
41. int movingCount(int m, int n, int k) {
    
42.     vector<vector<bool> > visit(m, vector<bool>(n, false));
    
43.     int c = 0;
    
44.     queue<pair<int, int> > que;
    
45. 
    
46.     pair<int, int> p = make_pair(0, 0);
    
47.     que.push(p);
    
48. 
    
49.     visit[p.first][p.second] = true;
    
50.     bfs(m, n, k, c, visit, que);
    
51.     return c;
    
52. }
    
53. 
    
54. 
    
55. 
    
56. int main(void){
    
57.         int m, n, k;
    
58.         cin >> m;
    
59.         cin.clear();
    
60.         cin >> n;
    
61.         cin.clear();
    
62.         cin >> k;
    
63.         cin.clear();
    
64.         int res = movingCount(m, n, k);
    
65.         cout << res << endl;
    
66.         return 0;
    
67.        
    
68. }

复制代码

注意事项：
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值。

糖逗

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