LC-剑指13 机器人的运动范围

剑指 Offer 13. 机器人的运动范围

class Solution {
    int ans = 0;
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        dfs(0, 0, m, n, k, visited);
        return ans;
    }
    /*思路： 向四个方向搜索，然后每个格子都进行判断，终止条件为超出边界和周围都不可达*/
    public void dfs(int mIdx, int nIdx, int m, int n, int k, boolean[][] visited) {
        if (mIdx<0 || mIdx>=m || nIdx<0 || nIdx>=n || visited[mIdx][nIdx]) {
            return;
        }
        int shuweihe = shuweihe(mIdx) + shuweihe(nIdx);
        if (shuweihe > k) {
            return;
        } else {
            ans++;
        }
        visited[mIdx][nIdx] = true;
        dfs(mIdx, nIdx-1, m, n, k, visited);
        dfs(mIdx, nIdx+1, m, n, k, visited);
        dfs(mIdx-1, nIdx, m, n, k, visited);
        dfs(mIdx+1, nIdx, m, n, k, visited);
        //visited[mIdx][nIdx] = false;
    }
    public int shuweihe(int num) {
        int res = num % 10;
        int chushu = num / 10;
        while (chushu != 0) {
            res += chushu % 10;
            chushu = chushu / 10;
        }
        return res;
    }
}