题目描述

blablabla

样例

blablabla

算法1

(dfs)

萌新小菜鸡写的dfs，看到这里没有dfs的答案就贴上来啦，以供后来的萌新参考hhh
大佬请无视QAQ

C++ 代码

class Solution {
public:
    int m, n;
    bool array[50][50] = { {false} };
    int movingCount(int threshold, int rows, int cols)
    {
        m = rows, n = cols;
        return dfs(threshold, 0, 0);
    }
    int sumxy(int x, int y) {//下标数位和
        int sum = 0;
        while (x || y) {
            sum += x % 10 + y % 10;
            x /= 10, y /= 10;
        }
        return sum;
    }
    int dfs(int threshold, int rows, int cols)
    {
        if (rows < 0 || rows >= m) return 0;
        if (cols < 0 || cols >= n) return 0;
        if (array[rows][cols]) return 0;
        if (sumxy(rows, cols) > threshold) return 0;

        array[rows][cols] = 1;
        return  dfs(threshold, rows - 1, cols) + \
                dfs(threshold, rows + 1, cols) + \
                dfs(threshold, rows, cols - 1) + \
                dfs(threshold, rows, cols + 1) + 1;
    }
};