一、題目描述
二、算法思路
這是?道非常典型的「搜索」類問題。
我們可以通過「深搜」或者「寬搜」，從 [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;}
}
