• 操作系統：ubuntu22.04
• IDE:Visual Studio Code
• 編程語言：C++11

題目描述

地上有一個 m 行 n 列的方格，從坐標 [0,0] 起始。一個機器人可以從某一格移動到上下左右四個格子，但不能進入行坐標和列坐標的數位之和大于 k 的格子。

例如：當 k = 18 時，機器人可以進入方格 [35, 39]（因為 3+5 + 3+9 = 20 > 18，所以不能進入）
問：機器人總共能到達多少個格子？

示例

輸入：m=2, n=3, k=1
輸出：3

解釋：

機器人從 [0,0] 出發，可到達以下格子：

• [0,0]
• [0,1]
• [0,2]

但 [1,0] 的數位和為 1+0=1 ≤ 1，也可以走；
但 [1,1] 的數位和為 1+1=2 > 1，不能進入。

所以總共有 3 個格子可以進入。

解法思路

這是一個典型的 搜索類問題，可以用：

深度優先搜索（DFS）
或 廣度優先搜索（BFS）

我們只需要從起點 (0, 0) 開始，向四個方向進行遞歸/遍歷，只要滿足條件就繼續探索，并統計所有能到達的格子。

代碼示例

#include <iostream>
#include <vector>using namespace std;class Solution {
public:int movingCount( int m, int n, int k ){vector< vector< bool > > visited( m, vector< bool >( n, false ) );return dfs( 0, 0, m, n, k, visited );}int dfs( int i, int j, int m, int n, int k, vector< vector< bool > >& visited ){// 邊界條件判斷 or 已訪問過 or 不滿足數位和條件if ( i < 0 || i >= m || j < 0 || j >= n || visited[ i ][ j ] || bitSum( i ) + bitSum( j ) > k )return 0;visited[ i ][ j ] = true;  // 標記為已訪問// 向四個方向探索return 1 + dfs( i + 1, j, m, n, k, visited ) + dfs( i - 1, j, m, n, k, visited ) + dfs( i, j + 1, m, n, k, visited ) + dfs( i, j - 1, m, n, k, visited );}// 計算一個整數的各位數字之和int bitSum( int x ){int sum = 0;while ( x > 0 ){sum += x % 10;x /= 10;}return sum;}
};// 測試代碼
int main()
{Solution solution;cout << solution.movingCount( 2, 3, 1 ) << endl;  // 輸出: 3cout << solution.movingCount( 3, 3, 0 ) << endl;  // 輸出: 1return 0;
}

運行結果

3
1