一、题目描述
二、算法思路
这是⼀道非常典型的「搜索」类问题。
我们可以通过「深搜」或者「宽搜」，从
[0, 0] 点出发，按照题目的要求（选择
向右移动一格 或
向下移动一格，但不能移动到衣柜之外
）一直往 [m - 1,
n - 1]
位置走。
同时，设置⼀个全局变量。每次走到⼀个合法位置，就将全局变量加一。当我们把所有能走到的路都走
完之后，全局变量里面存的就是最终答案。
三、解法
在这里我们使用的是floodfill算法。
题目要求是选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。对此，我们可以创建dx，dy两个移动数组，dx中的值表示当前行要加的数，dy中的值表示当前列要加的数。
令dx = {0,1}; dy = {1,0}，必须保证dx数组中的0对应dy数组中的1，dy数组中的1对应dy数组中的0。这样才能实现向右移动和向下移动。
我们举例来说明一下：
假设当前处于二维数组中下标为[1,2]的位置，
我们向右移动，则到达[1,3]。向右移动时，行不变，只需列+1；
向下移动，则到达[2,2]。向下移动时，列不变，只需行+1；
我们还要创建一个布尔类型的标记数组vis，将遍历过的位置标记一下，避免重复遍历。
递归函数：对于本题，我们的递归函数dfs，参数只需当前下标位置(int i ,int j)。
解决该题，我们还需要一个验证数位之和是否满足题目要求的函数。
四、解题代码
class Solution {
int m, n;
int[] dx = {0,1};
int[] dy = {1,0};
boolean[][] vis;
int cnt;
int ret; //统计结果
public int wardrobeFinishing(int _m, int _n, int _cnt) {
m = _m;
n = _n;
cnt = _cnt;
vis = new boolean[m][n];
dfs(0,0);
return ret;
}
public void dfs(int i, int j) {
ret++;
vis[i][j] = true;
//遍历dx,dy，相当于遍历向右、向下的位置
for(int k = 0; k < 2; k++) {
int x = i + dx[k];
int y = j + dy[k];
if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && check(x,y)) {
dfs(x,y);
}
}
}
public boolean check(int i, int j) {
int tmp = 0;
while(i != 0) {
tmp += i % 10;
i /= 10;
}
while(j != 0) {
tmp += j % 10;
j /= 10;
}
return tmp <= cnt;
}
}
