題目

地上有一個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。請問該機器人能夠到達多少個格子？

示例 1：

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

示例 2：

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

提示：

• 1 <= n,m <= 100
• 0 <= k?<= 20

解題思路

1.題目要求我們求出機器人能夠到達多少個格子，對于這道題我們依舊采用深度優先搜索來解決。

2.首先定義一個m行n列的布爾類型的visited數組，用來記錄每個格子是否被訪問過。然后定義一個dfs方法，用來進行深度優先搜索。在搜索過程中，如果當前格子的行或列小于0，或者大于等于m或n，或者當前格子已經被訪問過，或者當前格子的數字之和大于k，則返回0。否則，將當前格子標記為已訪問，并返回1加上向右、向下、向左、向上四個方向的dfs調用結果之和。

3.再定義一個sum方法，用來計算一個數字的每一位之和。首先定義一個res變量，并將其初始化為0。然后判斷x是否為0，如果不為0，則將res加上x的個位數，并將x除以10。最后返回res。

4.在movingCount方法中，首先初始化類成員變量m、n和k，并創建一個m行n列的visited數組。然后調用dfs方法，從矩陣的左上角開始搜索，并返回結果。

代碼實現

class Solution {int m;int n;int k;boolean[][] visited;public int movingCount(int m, int n, int k) {this.m = m;this.n = n;this.k = k;visited = new boolean[m][n];return dfs(0,0);}public int dfs(int i, int j){if(i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || k<sum(i)+sum (j)){return 0;}visited[i][j] = true;return 1 + dfs(i+1,j) + dfs(i,j+1) + dfs(i-1,j) + dfs(i,j-1);}int sum(int x){int res = 0;while(x != 0){res = res +(x % 10);x = x / 10;}return res;}
}

測試結果

?