C++--机器人的运动范围

题目

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

思路

• 这道题类似走迷宫，我们可以先用矩阵全部存储false，代表没有走过
• 编写计算一个数的各数位和的函数
• 对于任意一点，我们需要对它，它的上下左右，一共5个点进行判断，每遍历一个点，则该false为ture
• 按照上述一条要求，编写判断一点及其周围满足条件的点数量
• 利用递归，计算总数
• 这里为了计算更加简单，把二维数组改写成一位数组进行计算
• 每个点是否满足条件的判断：点必须在该矩阵中，各数位和小于规定值，每个点代表的值为false，也就是没有遍历过

C++代码测试

#include<iostream>
using namespace std;

//计算各数位的和
int sum(int n)
{
int result=0;
while(n)
{
result+=n%10;
n=n/10;
}
return result;
}

//计算一个点及四周满足条件的点数量
int moving(int threshold,int rows,int cols,int m,int n,bool *flag)
{
int count=0;
if(m>=0&&m<rows&&n>=0&&n<cols&&sum(m)+sum(n)<=threshold&&flag[m*cols+n]==false)
{
flag[m*cols+n]=true;
count=1+moving(threshold,rows,cols,m-1,n,flag)+moving(threshold,rows,cols,m+1,n,flag)+moving(threshold,rows,cols,m,n-1,flag)+moving(threshold,rows,cols,m,n+1,flag);
}

return count; }

//计算二维数组中满足条件的总点数
int movingCount(int threshold, int rows, int cols) { bool *flag=new bool[rows*cols]; for (int i=0;i<rows*cols;i++) flag[i]=false; int count=moving(threshold,rows,cols,0,0,flag); return count; }


int main()
{
	//测试代码
cout<<movingCount(18,100,100);

return 0;
}

  

 

  
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
 

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/102649128