【解题思路】
这道题说的不清楚,其实包含一个隐含条件:不可达的方格相当于障碍物,不能通过不可达的方格到达别的符合条件的方格。
如这个图中,上面那块符合条件的方格是可达的,但是无法到达下面符合条件的区域。
class Solution {
int num = 0;
int M, N, cnt, K;
int[][] dire = {{-1,0}, {0,1}, {1,0}, {0,-1}};
public int movingCount(int m, int n, int k) {
boolean[][] flag = new boolean[m][n];
M = m; N = n; cnt = m*n; K = k;
num = 0;
DFS(0, 0, 0, flag);
return num;
}
public void DFS(int n, int row, int col, boolean[][] flag)
{
if(n == cnt) return;
int tmp = 0, r = row, c = col;
while(r > 0)
{
tmp += r%10;
r = r/10;
}
while(c > 0)
{
tmp += c%10;
c = c/10;
}
if(tmp <= K) num++;
flag[row][col] = true;
for(int i = 0; i < 4; i++)
{
int newRow = row + dire[i][0];
int newCol = col + dire[i][1];
if(newRow < M && newRow >= 0 && newCol < N && newCol >= 0 && !flag[newRow][newCol])
{
DFS(n+1, newRow, newCol, flag);
}
}
}
}