AlgoPressAppearance
13-机器人的运动范围
题目描述
https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
地上有一个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
思路分析
回溯法：从左上角0,0开始探测，每次传入当前已经探测过的格子数，如果可以则继续往下探测，最后返回最大的格子数。
因为是要求机器人能够到达的多少个格子，所以不能重复计算，需要定义一个 visited 数组，表示已经走过该格子
注意放置好棋子之后，不能取回棋子，否则会出现重新放置计算步骤的方法
实现代码
csharp
public class Solution {
private int[,] visited;
private int DigitalSum(int num1, int num2){
int sum = 0;
while(num1 > 0){
sum += num1 % 10;
num1 = num1 / 10;
}
while(num2 > 0){
sum += num2 % 10;
num2 = num2 / 10;
}
return sum;
}
private int Place(int m, int n, int k, int[,] visited, int i, int j){
//如果不满足条件，就直接返回 0
if(i<0 || j <0 || i >= m || j >=n || DigitalSum(i,j) > k || visited[i,j] == 1){
return 0;
}
//放置本步
visited[i,j] = 1;
//放置下一步(4个方向)
int result1 = Place(m,n,k,visited,i-1,j);
int result2 = Place(m,n,k,visited,i+1,j);
int result3 = Place(m,n,k,visited,i,j-1);
int result4 = Place(m,n,k,visited,i,j+1);
//取回最后结果
int result = result1 + result2 + result3 + result4 + 1;
//取回棋子(此处不能取回棋子，否则会重新放置)
//visited[i,j] = 0;
return result;
}
public int MovingCount(int m, int n, int k) {
visited = new int[m,n];
int result = Place(m, n, k, visited, 0, 0 );
return result;
}
}
实现代码（第二遍）
csharp
public class Solution {
private bool[,] visited;
private int count; //记录总数
//计算数位和
private int digiSum(int i, int j){
int sum = 0;
while(i > 0){
sum += i % 10;
i = i / 10;
}
while(j > 0){
sum += j % 10;
j = j / 10;
}
return sum;
}
private void dfs(int m, int n, int i, int j, int k){
//越界检查
if(i < 0 || j < 0 || i >=m || j >=n || digiSum(i,j) > k || visited[i,j] == true){
return;
}
//符合条件
count++;
visited[i,j] = true;
//继续往下走
dfs(m,n,i+1,j,k);
dfs(m,n,i-1,j,k);
dfs(m,n,i,j+1,k);
dfs(m,n,i,j-1,k);
}
public int MovingCount(int m, int n, int k) {
//思路：深度搜索 记录总数
visited = new bool[m,n];
dfs(m,n,0,0,k);
return count;
}
}
复习：20220619
csharp
public class Solution {
int count = 0;
private int DigitalSum(int i,int j){
int sum = 0;
while(i>0){
sum += i % 10;
i = i / 10;
}
while(j>0){
sum += j % 10;
j = j / 10;
}
return sum;
}
private void dfs(int m, int n, int k, int i, int j, bool[,] used){
if(i<0 || i==m || j<0 || j==n || used[i,j] || DigitalSum(i,j) > k ){ //越界或使用过
return;
}
count ++;
used[i,j] = true;
dfs(m,n,k,i+1,j,used);
dfs(m,n,k,i-1,j,used);
dfs(m,n,k,i,j+1,used);
dfs(m,n,k,i,j-1,used);
}
public int MovingCount(int m, int n, int k) {
bool[,] used = new bool[m,n];
dfs(m,n,k,0,0,used);
return count;
}
}