编程练习
题目：地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路：机器人的走法有很多，每个坐标处都可以朝四个方向走，由阈值来圈定它的范围，因为路径是任意的，所以有多少种走法很难全部统计出来，只知道边界条件，内部的可能有很多，很容易想到回溯法，当机器人走到大于阈值的地方时回到上一步还在阈值内的坐标处，再朝剩下的方向走，直到再次出界，再退回，如此重复，记录它走过的格子，最后将所有满足情况的格子数相加返回即可。回溯法的思想很复杂，很难理解，还需好好消化。
要注意的点：坐标的转化，我采取了数字转字符串再转回数字的方法来处理坐标的位数和的计算，还有边界条件的判断。
java代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76import java.util.ArrayList;
public class MovingCount {
/**
* 回溯法：通过
* @param threshold
* @param rows
* @param cols
* @return
*/
public static int movingCount(int threshold, int rows, int cols)
{
boolean [] flag=new boolean[rows*cols];
return cango(threshold,0,0,rows,cols,flag);
}
/**
* 辅助函数用来统计还能继续走的格子数
* @param threshold 阈值
* @param i 当前位置的行号
* @param j 当前位置的列号
* @param rows 矩阵的行
* @param cols 矩阵的列
* @param flag 记录格子是否已经走过
* @return
*/
private static int cango(int threshold, int i, int j, int rows, int cols, boolean[] flag) {
int index=i*cols+j;
int indexSum=transform(i,j);
if(i<0 || j<0 || indexSum>threshold || i>=rows || j>=cols || flag[index]==true) {
return 0;
}
flag[index]=true;
return 1+cango(threshold,i-1,j,rows,cols,flag)
+cango(threshold,i+1,j,rows,cols,flag)
+cango(threshold,i,j-1,rows,cols,flag)
+cango(threshold,i,j+1,rows,cols,flag);
}
/**
* 用来将坐标值转换为可以和阈值相比较的位数相加的和，a,b为坐标值
* @param a
* @param b
* @return
*/
public static int transform(int a,int b) {
if(a<0 || b<0) {
return -1;
}
String s=String.valueOf(a);
String s1=String.valueOf(b);
char[] arr=s.toCharArray();
char[] arr1=s1.toCharArray();
int sum=0;
ArrayList<Integer> list=new ArrayList<Integer>();
//将分割开的位数分别加入到list中
for(int i=0;i<arr.length;i++) {
list.add(Integer.parseInt(arr[i]+""));
}
for(int j=0;j<arr1.length;j++) {
list.add(Integer.parseInt(arr1[j]+""));
}
for(int h:list) {
sum+=h;
}
return sum;
}
public static void main(String[] args) {
System.out.println(movingCount(8, 3, 3));
}
}