剑指offer-机器人的运动范围

xiaoxiao2021-03-01  6

题目 地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移动,它每一次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格(35, 37),因为3+5+3+7=18。但它不能进入方格(35, 38),因为3+5+3+8=19。请问该机器人能够到达多少个格子? 思路 回溯法,走出一步,就看能不能走四周的格子。 代码

int MovingCount(int treshold,int rows,int cols) { if(treshold<0||rows<0||cols<0) { return 0; } int*visited=new int[rows*cols]; for(int i=0;i<rows*cols;i++) visited[i]=0; int row=0; int col=0; int count=MovingCountCore(treshold,rows,cols,row,col,visited); delete[]visited; return count; } int MovingCountCore(int treshold,int rows,int cols,int row,int col,int*visited) { int count=0; if(check(treshold,rows,cols,row,col,visited)) { visited[row*cols+col]=1; count=1+MovingCountCore(treshold,rows-1,cols,row,col,visited)+ MovingCountCore(treshold,rows,cols,row,col-1,visited)+ MovingCountCore(treshold,rows,cols,row+1,col,visited)+ MovingCountCore(treshold,rows,cols,row,col+1,visited); } } bool check(int treshold,int rows,int cols,int row,int col,int*visited) { int rownum=getdigit(row); int colnum=getdigit(col); if(treshold>=(rownum+colnum)&&row>=0&&row<rows&&col>=0&&col<cols&&!visited[row*cols+col]) return true; else return false; } int getdigit(int k) { int sum=0; while(!k) { sum+=(k%10); k=k/10 } return sum; }
转载请注明原文地址: https://www.6miu.com/read-3100148.html

最新回复(0)