本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖
面試題13：機(jī)器人的運(yùn)動(dòng)范圍
題目要求：
地上有一個(gè)m行n列的方格，一個(gè)機(jī)器人從坐標(biāo)(0,0)的各自開始移動(dòng)酒贬，它每次可以向上下左右移動(dòng)一格问慎，但不能進(jìn)入橫縱坐標(biāo)數(shù)位之和大于k的格子探熔。
例如昌阿，當(dāng)k等于18時(shí)梢夯，機(jī)器人能進(jìn)入(35,37)言疗，因?yàn)?+5+3+7=18；但卻不能進(jìn)入(35,38)厨疙，因?yàn)?+5+3+8=19>18。
請(qǐng)問該機(jī)器人能夠到達(dá)多少個(gè)格子疑务。
解題思路：
本題依舊考察回溯法沾凄。
每前進(jìn)一步后，可選移動(dòng)項(xiàng)為上下左右四個(gè)知允；為了判斷某一個(gè)格子是否可以進(jìn)入從而進(jìn)行計(jì)數(shù)撒蟀，不僅需要考慮邊界值，計(jì)算各位數(shù)字之和温鸽，更要判斷該格子是否已經(jīng)被訪問過保屯，手负。所以需要一個(gè)布爾矩陣，用來記錄各格子是否已被訪問姑尺。整體思路與12題類似竟终，具體請(qǐng)參考本系列的導(dǎo)航帖。
package chapter2;
/**
* Created by ryder on 2017/7/4.
* 機(jī)器人的運(yùn)動(dòng)范圍
*/
public class P92_RobotMove {
//依舊回溯
public static int movingCount(int threshold,int rowLen,int colLen){
if(rowLen<=0 || colLen<=0 || threshold<0)
return 0;
boolean[][] visitFlag = new boolean[rowLen][colLen];
for(int row=0;row<rowLen;row++){
for(int col=0;col<colLen;col++)
visitFlag[row][col] = false;
}
return movingCountCore(threshold,rowLen,colLen,0,0,visitFlag);
}
public static int movingCountCore(int threshold,int rowLen,int colLen,int row,int col,boolean[][] visitFlag){
int count = 0;
if(canGetIn(threshold,rowLen,colLen,row,col,visitFlag)){
visitFlag[row][col] = true;
count = 1+movingCountCore(threshold,rowLen,colLen,row-1,col,visitFlag)+
movingCountCore(threshold,rowLen,colLen,row+1,col,visitFlag)+
movingCountCore(threshold,rowLen,colLen,row,col-1,visitFlag)+
movingCountCore(threshold,rowLen,colLen,row,col+1,visitFlag);
}
return count;
}
public static boolean canGetIn(int threshold,int rowLen,int colLen,int row,int col,boolean[][] visitFlag){
return row>=0 && col>=0 && row<rowLen
&& col<colLen && !visitFlag[row][col]
&& getDigitSum(row)+getDigitSum(col)<=threshold;
}
public static int getDigitSum(int number){
int sum=0;
while (number>0){
sum += number%10;
number/=10;
}
return sum;
}
public static void main(String[] args){
System.out.println(movingCount(0,3,4)); //1
System.out.println(movingCount(1,3,4)); //3
System.out.println(movingCount(9,2,20)); //36
}
}
運(yùn)行結(jié)果
1
3
36
