题目描述:
题目链接戳此
解题思路:
这题和上题矩阵中的路径可以对比起来看,同样也是深度优先搜索(DFS)。由于机器人从[0][0]位置向下向右探索,右边的下面和下面的右边可能会重复,所以可以将走过的路径记录下来置为true防止重复走。
代码实现如下:
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
return dfs(m,n,0,0,k,visited);
}
public int dfs(int m,int n,int i,int j,int k,boolean[][] visited) {
if (i / 10 + i % 10 + j / 10 + j % 10 > k) return 0;//题目指明只有两位数
if (i > m - 1 || j > n - 1 || visited[i][j]) return 0;
visited[i][j] = true;
return dfs(m,n,i + 1,j,k,visited) + dfs(m,n,i,j + 1,k,visited) + 1;
}
}