剑指offer算法题-JZ66

题目描述

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

解答：（见代码注释）

function movingCount(threshold, rows, cols) { // write code here //用来存放能达到的格子数 var count=0 for(var i=0;i<rows;i++){ for(var j=0;j<cols;j++){ var adds=add(i,j) //它不会每一行都遍历，在某一行第一格断开的时候，后面都将无法进行 if(add(i,0)>threshold){ return count } if(adds<=threshold){ count++ }else if(i>=1&&adds>threshold&&(j+1<cols)){ //此处的意思是，如果在第i行第j列不能达到， //而（i,j+1）和（i-1，j+1）可以达到的话， //则可以通过上一行向下一格进入下一行，让j++， //后面继续满足此特点 //count就继续累加 for(j=j+1;j<cols;j++){ while(add(i-1,j)<=threshold&&add(i,j)<=threshold){ count++ j++ } } }else{ //如果均不满足，直接让内层循环锁死，进入下一行判断 j=cols } } } return count } //封装一个子函数add，用来计算行列各数位的数字相加的和 function add(rows,cols){ var rowstr=''+rows var rowlen=rowstr.length var colstr=''+cols var collen=colstr.length var row=0 var col=0 for(var i=0;i<rowlen;i++){ row+=parseInt(rowstr[i]) } for(var i=0;i<collen;i++){ col+=parseInt(colstr[i]) } return row+col }