题目
地上有一个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动，它每次可以向左、右、上、下移动一格，但不能进入行坐标与列坐标的位数之和大于k的格子。例如，当k为18时，机器人能够进入方格(35,37)，因为3+5+3+18.但是不能进入方格(35,38)，因为3+5+3+8=19。请问机器人能够达到多少个格子
分析
dfs + 回溯
我们可以设置一个二维数组用来区别该位置是否计算过。初始化成0，如果计算过就设置为-1。然后从(0,0)开始，如果(0,0)都不符合那就所有位置都不符合了。然后与依次向上、下、左、右遍历。如下k=5时
绿色表示机器人可以到达的位置，
蓝色表示机器人不可以到达的位置，但是坐标符合。
空白就是坐标不符合
分析上图，我们发现9到10，19到20是零界点。
再测试k=11
总结上图。我们可以发现从(0,0)开始向下和向右移动就可以到达所有绿色区域，
C
#include<stdio.h> #include<stdlib.h> int getDigitSum(int num); int movingCount(int rows, int cols, int k); int movingCountCore(int** test, int rows, int cols, int i, int j, int k); int main() { int k = 5; int ret = movingCount(80, 100, k); if (-1 == ret) { printf("行或列小于零\n"); } else { printf("机器人能够到达%d个格子\n", ret); } return 0; } int movingCount(int rows, int cols, int k) { if (rows <= 0 || cols <= 0) { return -1; } int** test = (int**)calloc(rows * cols, sizeof(int));//申请一个标志数组 if (NULL == test) { perror("申请空间失败"); } int count = movingCountCore(test, rows, cols, 0, 0, k); free(test);//释放test数组 return count; } int movingCountCore(int** test, int rows, int cols, int i, int j, int k) { //行列超出边界，或者test[i][j]的值已经被修改，或者行坐标和列坐标的数位之和大于k的格子 if (i >= rows || j >= cols || *((int*)test + i * cols + j) != 0 || (getDigitSum(i) + getDigitSum(j)) > k) { return 0; } *((int*)test + i * cols + j) = -1; //依次向下、右遍历 return 1+ movingCountCore(test, rows, cols, i + 1, j, k) + movingCountCore(test, rows, cols, i, j + 1, k); } int getDigitSum(int num)//坐标的位数之和 { int sum = 0; while (num != 0) { sum += num % 10; num /= 10; } return sum; }
分析一下坐标的位数和：
当 0 <= i <= 9时，位数和就是本身
当 10 <= i <=19时，位数和是1+个位数
当 11 <= i <= 29时，位数和是2+个位数
位数和 = i %10 + 个位数
那么我们就可以省去getDigitSum()函数了。
优化后：
C
#include<stdio.h> #include<stdlib.h> int movingCount(int rows, int cols, int k); int movingCountCore(int** test, int rows, int cols, int i, int j, int k); int main() { int k = 5; int ret = movingCount(80, 100, k); if (-1 == ret) { printf("行或列小于零\n"); } else { printf("机器人能够到达%d个格子\n", ret); } return 0; } int movingCount(int rows, int cols, int k) { if (rows <= 0 || cols <= 0) { return -1; } int** test = (int**)calloc(rows * cols, sizeof(int));//申请一个标志数组 if (NULL == test) { perror("申请空间失败"); } int count = movingCountCore(test, rows, cols, 0, 0, k); free(test);//释放test数组 return count; } int movingCountCore(int** test, int rows, int cols, int i, int j, int k) { //行列超出边界，或者test[i][j]的值已经被修改，或者行坐标和列坐标的数位之和大于k的格子 if (i >= rows || j >= cols || *((int*)test + i * cols + j) != 0 || (i % 10 + i / 10 + j % 10 + j / 10) > k) { return 0; } *((int*)test + i * cols + j) = -1; //依次向下、右遍历 return 1+ movingCountCore(test, rows, cols, i + 1, j, k) + movingCountCore(test, rows, cols, i, j + 1, k); }
本章完！
