问题描述
家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。
整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。
请返回整理师 总共需要整理多少个格子。
原问题有些描述不清，这里其实是问，可以整理的格子连成一片一片的，最大的那一片有多少格？
题解
DFS、BFS遍历即可解，最大的那一块一定包含(0,0)，所以从(0,0)开始向右向下DFS。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
boolean[][] visited;
int m,n,cnt;
public int wardrobeFinishing(int m, int n, int cnt) {
this.m=m;this.n=n;this.cnt=cnt;
this.visited = new boolean[m][n];
return DFS(0,0);
}
public int digit(int i){
int res = 0;
while(i>0){
res+=i%10;
i/=10;
}
return res;
}
public int DFS(int i,int j){
if(i>=m||j>=n||visited[i][j]||digit(i)+digit(j)>cnt) return 0;
visited[i][j]=true;
return DFS(i+1,j)+DFS(i,j+1)+1;
}
}
|