劍指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。

注意:

1. 0<=m<=50
2. 0<=n<=50
3. 0<=k<=100

?

BFS和DFS的區別以及總結：ref[https://blog.csdn.net/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;
}