機(jī)器人的運(yùn)動(dòng)范圍
題目描述
地上有一個(gè)m行n列的方格，從坐標(biāo) [0,0] 到坐標(biāo) [m-1,n-1] 。一個(gè)機(jī)器人從坐標(biāo) [0, 0] 的格子開始移動(dòng)，它每次可以向左、右、上、下移動(dòng)一格（不能移動(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。請問該機(jī)器人能夠到達(dá)多少個(gè)格子？
示例：
輸入：m = 2, n = 3, k = 1
輸出：3
輸入：m = 3, n = 1, k = 0
輸出：1
提示：
1 <= n,m <= 100
0 <= k <= 20
題目分析
這題的思路和 面試題12. 矩陣中的路徑 非常像，甚至比12題更加簡單，都是從當(dāng)前點(diǎn)往四個(gè)方向探索，而這題簡單的地方在于不用回溯，如果行不通直接返回0就行；具體流程如下：
- 如果當(dāng)前節(jié)點(diǎn)不符合條件，意味著當(dāng)前節(jié)點(diǎn)阻塞，不能往下探索，所以收獲為0，直接返回
- 如果當(dāng)前節(jié)點(diǎn)符合條件，意味著從當(dāng)前點(diǎn)開始，最少能收獲1，具體的收獲值為1+四個(gè)方向的收獲值之和，需要注意的是，這里仍需要一個(gè)visited數(shù)組來標(biāo)明哪些節(jié)點(diǎn)已經(jīng)訪問過了，不然會(huì)造成重復(fù)
- 從[ 0, 0 ]開始深度優(yōu)先遍歷，按照上面的流程走完，done
而在這題里計(jì)算一個(gè)數(shù)的分解結(jié)果我用一個(gè)sumOfNum數(shù)組來存放，例如142的分解結(jié)果為1+4+2=7，所以sumOfNum[142] = 7，這樣可以解決重復(fù)分解（a[142][2]和a[345][142]都需要142的分解結(jié)果）；
boolean[][] visited;
int[][] direction = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int[] sumOfNum;
int m, n;
public int movingCount(int m, int n, int k) {
visited = new boolean[m][n];
this.m = m;
this.n = n;
sumOfNum = new int[m > n ? m : n];
for (int i = 0; i < sumOfNum.length; i++)
sumOfNum[i] = -1;
return canVisited(0, 0, k);
}
public int getSum(int a) {
if (sumOfNum[a] != -1)
return sumOfNum[a];
int tmp = a;
sumOfNum[a] = 0;
while (a > 0) {
sumOfNum[tmp] += (a % 10);
a /= 10;
}
return sumOfNum[tmp];
}
public int canVisited(int x, int y, int k) {
if (x < 0 || y < 0 || x == m || y == n || visited[x][y])
return 0;
if (getSum(x) + getSum(y) > k)
return 0;
visited[x][y] = true;
int sum = 1;
for (int i = 0; i < 4; i++) {
sum += canVisited(x + direction[i][0], y + direction[i][1], k);
}
return sum;
}
