剑指offer：面试题13. 机器人的运动范围

首页 > 剑指offer：面试题13. 机器人的运动范围

剑指offer：面试题13. 机器人的运动范围

题目：机器人的运动范围

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

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

示例 2：

输入：m = 3, n = 1, k = 0
输出：1

提示：

1 <= n,m <= 100
0 <= k <= 20

解题：

本题使用的方法同样还是回溯法，另外还需要会计算给定整数上的各个位上数之和。
使用一个访问数组记录是否已经经过该格子。
机器人从(0,0)开始移动，当它准备进入(i,j)的格子时，通过检查坐标的数位来判断机器人是否能够进入。
如果机器人能进入(i,j)的格子，接着在判断它是否能进入四个相邻的格子(i,j-1),(i,j+1),(i-1,j),(i+1,j)。
因此，可以用回溯法来解决这一问题。

public class Solution {//回溯法public int movingCount(int threshold, int rows, int cols) {if(rows<=0||cols<=0||threshold<0)   return 0;int[] visited=new int[rows*cols];return MovingCount(threshold,rows,cols,0,0,visited);}private int MovingCount(int threshold,int rows,int cols,int row,int col,int[] visited){int count=0;if(canWalkInto(threshold, rows, cols, row, col, visited)){visited[row*cols+col]=1;count=1+MovingCount(threshold,rows,cols,row-1,col,visited)   //往上+MovingCount(threshold,rows,cols,row+1,col,visited)  //往下+MovingCount(threshold, rows, cols, row, col-1, visited)   //往左+MovingCount(threshold, rows, cols, row, col+1, visited);  //往右}return count;}private boolean canWalkInto(int threshold,int rows,int cols,int row,int col,int[] visited){if(row>=0 && row=0 && col


            
                
                    更多相关：
                    
                        
                    
                        java 读取excel_Java12POI操作Excel
                    
                    
                        
                                    Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...
                            
                        
                    
				

                    
                        C++ 生成随机数
                    
                    
                        
                            要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 
要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 
要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 
通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 
要取得a到b之间的...
                            
                        
                    
				

                    
                        基于C++的本征图像分解(Intrinsic Image Decomposition)
                    
                    
                        
                            利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。
Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...
                            
                        
                    
				

                    
                        剑指offer：面试题39. 数组中出现次数超过一半的数字
                    
                    
                        
                            题目：面试题39. 数组中出现次数超过一半的数字 
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 
你可以假设数组是非空的，并且给定的数组总是存在多数元素。 
示例 1: 
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2 
限制： 
1 <= 数组长度 <= 50000 

解题： 
cl...
                            
                        
                    
				

                    
                        剑指offer：面试题33. 二叉搜索树的后序遍历序列
                    
                    
                        
                            题目：二叉搜索树的后序遍历序列 
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 
参考以下这颗二叉搜索树： 
     5     /     2   6   /   1   3示例 1： 
输入: [1,6,3,2,5]
输出...
                            
                        
                    
				

                    
                        【转】mysql-status和variables区别
                    
                    
                        
                            转：http://www.2cto.com/database/201304/204320.html  mysql之status和variables区别  首先可以通过下属两个命令来查看mysql的相应的系统参数 show status like '%abc%'; show variables like '%abc%';  但是很多人不...