回溯-機(jī)器人的運(yùn)動(dòng)范圍
題目描述
地上有一個(gè)m行和n列的方格陵珍。一個(gè)機(jī)器人從坐標(biāo)0,0的格子開(kāi)始移動(dòng)哎榴，每一次只能向左，右僵蛛，上尚蝌，下四個(gè)方向移動(dòng)一格，但是不能進(jìn)入行坐標(biāo)和列坐標(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苛预。請(qǐng)問(wèn)該機(jī)器人能夠達(dá)到多少個(gè)格子句狼？
public class Solution {
/*解題思路：回溯法
1.從(0,0)開(kāi)始走，每成功走一步標(biāo)記當(dāng)前位置為true,然后從當(dāng)前位置往四個(gè)方向探索热某，返回1 + 4 個(gè)方向的探索值之和腻菇。
2.探索時(shí)，判斷當(dāng)前節(jié)點(diǎn)是否可達(dá)的標(biāo)準(zhǔn)為：
1）當(dāng)前節(jié)點(diǎn)在矩陣內(nèi)昔馋；
2）當(dāng)前節(jié)點(diǎn)未被訪(fǎng)問(wèn)過(guò)筹吐；
3）當(dāng)前節(jié)點(diǎn)滿(mǎn)足limit限制。*/
public int movingCount(int threshold, int rows, int cols)
{
boolean[][] unvisited=new boolean[rows][cols];
return moving(threshold,rows,cols,unvisited,0,0);
}
public int moving(int threshold,int rows,int cols,boolean[][]unvisited,int i,int j){
if(threshold<=0||i<0||i>=rows||j<0||j>=cols
||unvisited[i][j]||(sum(i)+sum(j)>threshold)){
return 0;
}
unvisited[i][j]=true;//初始化秘遏，當(dāng)前節(jié)點(diǎn)未被訪(fǎng)問(wèn)過(guò)
return moving(threshold,rows,cols,unvisited,i-1,j) //左丘薛，右，下邦危，上
+moving(threshold,rows,cols,unvisited,i+1,j)
+moving(threshold,rows,cols,unvisited,i,j-1)
+moving(threshold,rows,cols,unvisited,i,j+1)
+ 1;
}
public int sum(int i){
int sum=0;
while(i!=0){
sum+=i%10;
i/=10;
}
return sum;
}
}
