博客

题目

：地上有一个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动，它每一次可以向左右上下移动一格，但不能进入行坐标和列坐标之和大于K的格子。例如，当k为18的时，机器人能够进入的方格（35,37），因为3+5+3+7=18.但是它不能进入方格（35,38），因为3+5+3+8=19。请问该机器人能够到达多少个格子？

这道题目，《剑指offer》当中也是用了回溯法，所以此题我也是用回溯法做的。与


C语言：矩阵中的路径

非常相似，只是这道题目要求计算的是方格数目，所以在上道题目中很多输出true或false的地方，本题需要输出的是方格的总数。

核心判断函数当中，需要计算某个方格上、下、左、右方格中满足条件的方格总和而不是判断真假了。

本题我编写了功能测试（test1）和边界测试（test2~test4）两种测试用例来检验函数。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define true 1
#define false 0

int move_range(int k, int rows, int cols) {
	if ((k < 0) || (rows <= 0) || (cols <= 0))
		return 0;

	int *visited = (int *)malloc((rows * cols) * sizeof(int));
	memset(visited, 0, (rows * cols) * sizeof(int));

	int count = move_range_count(k, 0, 0, rows, cols, visited);
	free(visited);
	return count;
}

int move_range_count(int k, int row, int col, int rows, int cols,int* visited) {

	int count = 0;
	if (check(k, row, col, rows, cols, visited)) {

		visited[row * cols + col] = true;

		count = 1 + move_range_count(k, row, col - 1, rows, cols, visited)
			+ move_range_count(k, row, col + 1, rows, cols, visited)
			+ move_range_count(k, row - 1, col, rows, cols, visited)
			+ move_range_count(k, row + 1, col, rows, cols, visited);
	}
	return count;
}

int check(int k, int row, int col, int rows, int cols, int* visited) {
	if ((row >= 0) && (row < rows) && (col >= 0) && (col < cols) && sum(row, col, k) && (!visited[row * cols + col])) {
		return true;
	}
	return false;
}

int sum(int row, int col, int k) {
	int sum = 0;
	while (row > 0) {
		sum = sum + row % 10;
		row = row / 10;
	}

	while (col > 0) {
		sum = sum + col % 10;
		col = col / 10;
	}

	if (sum <= k)
		return true;
	
	return false;
}

//功能测试
void test1() {
	int count = 0;
	int m = 5, n = 5, k = 7;

	/*若题目要求从键盘获取m,n,k,使用下面的方法初始化这三个值*/
	//int m, n, k;
	//printf("请输入行数m: ");
	//scanf("%d", &m);
	//printf("请输入列数n: ");
	//scanf("%d", &n);
	//printf("请输入基准数k: ");
	//scanf("%d", &k);

	int *matrix = (int*)malloc((m * n) * sizeof(int));

	count = move_range(k, m, n);
	free(matrix);
	printf("test1:机器人能到达的格子数为: %d\n",count);
}

//边界测试
void test2() {
	int count = 0;
	int m = 0, n = 5, k = 7;
	int *matrix = (int*)malloc((m * n) * sizeof(int));

	count = move_range(k, m, n);
	free(matrix);
	printf("test2:机器人能到达的格子数为: %d\n", count);
}

//边界测试
void test3() {
	int count = 0;
	int m = 5, n = 5, k = -2;

	int *matrix = (int*)malloc((m * n) * sizeof(int));

	count = move_range(k, m, n);
	free(matrix);
	printf("test3:机器人能到达的格子数为: %d\n", count);
}

//边界测试
void test4() {
	int count = 0;
	int m = 0, n = -1, k = 7;

	int *matrix = (int*)malloc((m * n) * sizeof(int));

	count = move_range(k, m, n);
	free(matrix);
	printf("test4:机器人能到达的格子数为: %d\n", count);
}

void main() {

	test1();
	test2();
	test3();
	test4();
}

运行结果：