【66】机器人的运动范围

【66】机器人的运动范围

时间限制：1秒空间限制：32768K回溯法

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

---

VS2010代码：

// Source: http://www.nowcoder.com/practice/6e5207314b5241fb83f2329e89fdecc8?tpId=13&tqId=11219&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking // Author: Yang Qiang // Date : 2016-8-15 #include<iostream> using namespace std; ///思路分析： //1.机器人路径范围是一个连通区域。因此要把可达范围都记录一下。 //2.要对每个位置的四个方向均作出判断。 class Solution { /********位和控制函数函数****************/ //超出控制范围,返回0，否则返回1； bool SumOfBit(int threshold1,int curRow, int curCol) { int SumBit=0; while(curRow) { SumBit=SumBit+curRow%10; curRow=curRow/10; } while(curCol) { SumBit=SumBit+curCol%10; curCol=curCol/10; } return SumBit>threshold1?0:1; } /**********路径寻找函数**********/ //输入：控制阈值,矩阵行列;当前行列,标志矩阵 //输出改点是否能继续前进 void FindPath(int threshold1, int rows1, int cols1, int curRow, int curCol, int* flag) { //边界控制:超出边界,该方向无法继续 if(curRow<0 || curCol<0 || curRow>rows1-1 || curCol>cols1-1) return; //位和控制:位和不满足,该方向无法继续 if(!SumOfBit(threshold1,curRow,curCol) ) return; //标志位控制:已走过的路径不再继续 if(flag[curRow*cols1+curCol]==1) return; //当前位置通过监测,更新标志位,继续搜索 flag[curRow*cols1+curCol]=1; FindPath( threshold1,rows1,cols1, curRow-1, curCol, flag); //向上 FindPath( threshold1,rows1,cols1, curRow, curCol+1, flag); //向右 FindPath( threshold1,rows1,cols1, curRow+1, curCol, flag); //向下 FindPath( threshold1,rows1,cols1, curRow, curCol-1, flag); //向左 //bool hasPath=0; //hasPath=FindPath( threshold1,rows1,cols1, curRow-1, curCol, flag) //向上 // || FindPath( threshold1,rows1,cols1, curRow, curCol+1, flag) //向右 // || FindPath( threshold1,rows1,cols1, curRow+1, curCol, flag) //向下 // || FindPath( threshold1,rows1,cols1, curRow, curCol-1, flag); //向左 //如果该位置的四周都不行 /*if(!hasPath) return*/ } public: int movingCount(int threshold, int rows, int cols) { //非法情况定义 if(threshold<0 || rows<1 || cols<1) return 0; //定义一个标志矩阵，记录走过的路径。 int* Flag=new int[rows*cols]; for(int i=0; i<rows*cols; i++) Flag[i]=0; //初始化一次标志位 //寻找路径，并标记 FindPath( threshold,rows,cols, 0, 0, Flag); //遍历矩阵，找出标记的个数。 int reachedNum=0; for(int i=0; i<rows*cols; i++) { if(Flag[i]==1) reachedNum++; //初始化一次标志位 } return reachedNum; } }; int main() { Solution s1; cout<<s1.movingCount(5,4,4)<<endl; }

牛客网通关图片：

另附（剑指offer）66道通关卡片：