剑指offer.机器人的运动范围

地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼∼n−1。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。但是不能进入行坐标和列坐标的数位之和大于 kk 的格子。请问该机器人能够达到多少个格子？

样例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<=500<=n<=500<=k<=100

BFS和DFS的区别以及总结：ref[/wanglin007/article/details/82054813]

DFS：DFS算法是一个对连通图进行遍历的算法，它的思想是从一个被选定的点出发一条路走到底，如果得不到目的解，那就返回到上一个节点，然后换一条路继续走到底，直到找到目的解返回或者全部遍历完返回一个事先定好的值。DFS一般借用递归完整整个算法的构造。

int dfs(){If(达到目的)处理return;else{处理;dfs();}}

BFS:BFS是一个对连通图进行遍历的算法，主要思想就是从一个被选定的点出发，然后从这个点的所有方向每次只走一步。与dfs不同的是，bfs不是运用的递归，而是运用队列和函数内循环构造的。

void bfs(){queue<数据类型>q;q.push(数据变量); while(!q.empty()){数据类型 t; t=q.front();q.pop();}}

本题就使用BFS来进行求解。

class Solution{punlic:int get_Single(int x){int sum = 0;while(x){sum += x % 10;x /= 10;}return sum;}int getSum(pair<int, int> p){return get_Single(p.first)+get_Single(p.second);}int movingCount(int threshold, int rows, int cols){int res;if(rows == 0 || cols == 0)return 0;}//定义一个布尔类型数字，标志是否被访问过vector<vector<bool>> st(rows, vector<bool>(cols));queue<pair<int, int>> q;q.push({0,0});int dx[4] = {-1, 0 ,1 , 0};int dy[y] = {0, 1, 0 ,-1};while(q.size()){auto t = q.front();q.pop();if(getSum(t) > threshold || st[t.first][t.second]){continue;}else{res++;st[t.first][t.second] = true;}//开始上下左右四个方向移动for(int i = 0 ; i < 4; i++){int a = t.first + dx[i];int b = t.second + dy[i];if(a >= 0 && a < rows && b >= 0 && b < cols){q.push({a,b});}}}return res;}