题目描述: 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子? 解题思路: 利用递归实现,每次只能走上下左右四个点,进行判断点的位置是否越界,点数之和是否大于K,是否已经走过了。
题目描述:
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?
解题思路:
利用递归实现,每次只能走上下左右四个点,进行判断点的位置是否越界,点数之和是否大于K,是否已经走过了。
1 public class Solution {
2 public int movingCount(int threshold, int rows, int cols)
3 {
4 int flag[][]=new int[rows][cols];//记录是否走过
5 return helper(0,0,rows,cols,flag,threshold);
6 }
7
8 private int helper(int i,int j,int rows,int cols,int [][] flag,int threshold){
9 if(i=rows || j=cols || numSum(i)+numSum(j)> threshold || flag[i][j]==1){
10 return 0;
11 }
12 flag[i][j]=1;//走过的位置设置为1
13 return helper(i-1,j,rows,cols,flag,threshold)
14 +helper(i+1,j,rows,cols,flag,threshold)
15 +helper(i,j-1,rows,cols,flag,threshold)
16 +helper(i,j+1,rows,cols,flag,threshold)+1;
17 }
18
19 //行坐标和列坐标的数位之和
20 private int numSum(int i){
21 int sum=0;
22 while(i>0){
23 sum += i % 10;
24 i = i / 10;
25 }
26 return sum;
27 }
Original: https://www.cnblogs.com/lkylin/p/13502854.html
Author: 手下留情
Title: 剑指Offer:机器人的运动范围(13)
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/564835/
转载文章受原作者版权保护。转载请注明原作者出处!