地上有一個m行n列的方格，一個機器人從坐標（0，0）的格子開始移動，它每次可以向上下左右移動一個格子，但不能進入行坐標和列坐標的位數之和大于k的格子，請問機器人能夠到達多少個格子

#include <vector> // 包含vector頭文件
#include <queue> // 包含queue頭文件class Solution { // 定義解決方案類
private:int getSum(int x, int y) { // 計算坐標數位之和int sum = 0; // 初始化和為0while (x > 0) { // 處理x坐標sum += x % 10; // 加上個位數x /= 10; // 去掉個位數}while (y > 0) { // 處理y坐標sum += y % 10; // 加上個位數y /= 10; // 去掉個位數}return sum; // 返回數位之和}public:int movingCount(int m, int n, int k) { // 計算可到達的格子數if (k < 0) return 0; // 如果k小于0，無法移動std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false)); // 記錄已訪問的格子std::queue<std::pair<int, int>> q; // 用于BFS的隊列int count = 0; // 可到達的格子數q.push({0, 0}); // 起始點加入隊列visited[0][0] = true; // 標記起始點為已訪問int dx[4] = {-1, 1, 0, 0}; // x方向的移動int dy[4] = {0, 0, -1, 1}; // y方向的移動while (!q.empty()) { // BFS主循環auto [x, y] = q.front(); // 獲取當前格子坐標q.pop(); // 從隊列中移除count++; // 增加可到達的格子數for (int i = 0; i < 4; i++) { // 嘗試四個方向的移動int nx = x + dx[i], ny = y + dy[i]; // 計算新坐標if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && getSum(nx, ny) <= k) { // 檢查新坐標是否有效q.push({nx, ny}); // 將新坐標加入隊列visited[nx][ny] = true; // 標記新坐標為已訪問}}}return count; // 返回可到達的格子數}
};

這個實現使用了廣度優先搜索（BFS）算法來解決問題。以下是主要的設計思路：

1. 我們定義了一個Solution類，其中包含兩個主要函數：
   • getSum: 這是一個私有輔助函數，用于計算坐標的數位之和。
   • movingCount: 這是公共接口函數，用于計算機器人能夠到達的格子數量。
2. 在movingCount函數中：
   • 我們使用一個二維布爾數組visited來記錄已經訪問過的格子。
   • 使用一個隊列q來進行BFS。
   • 從(0,0)開始，將其加入隊列并標記為已訪問。
   • 使用一個while循環進行BFS，每次從隊列中取出一個格子，然后嘗試向四個方向移動。
   • 對于每個新的可能位置，我們檢查：
     1. 是否在網格范圍內
     2. 是否已經被訪問過
     3. 數位之和是否不大于k
   • 如果滿足所有條件，我們將新位置加入隊列，并標記為已訪問。
   • 每訪問一個新的格子，我們就將計數器加1。
3. 最后返回計數器的值，即為機器人能夠到達的格子數量。

這個算法的時間復雜度為O(mn)，其中m和n分別是網格的行數和列數。空間復雜度也是O(mn)，主要用于存儲visited數組和BFS隊列。