题目描述

地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。

一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

请问该机器人能够达到多少个格子？

样例

输入：k=18, m=40, n=40

输出：1484

解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
      但是，它不能进入方格（35,38），因为3+5+3+8 = 19。

算法1

(暴力枚举DFS)

1. ans全局变量，记录满足条件的个数
2. 整个棋盘看作状态不需要回溯

时间复杂度 $O(n^2)$

C++ 代码

class Solution {
public:
    int ans = 0;

    int movingCount(int threshold, int rows, int cols){
        if(!rows || !cols ) return ans;//特判rows == 0 或 cols == 0
        vector<vector<bool>> st(rows, vector<bool>(cols));
        dfs(threshold, 0, 0, rows, cols, st);
        return ans;
    }

    void dfs(int k, int x, int y, int row, int col, vector<vector<bool>>& st){
         //x%10 + x/10 + y%10 + y/10 > k
         if(x%10 + x/10 + y%10 + y/10 > k) return;
         //x%10 + x/10 + y%10 + y/10 <= k
         ans++;
         st[x][y] = true;
         int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
         for(int i = 0; i < 4; i++){
            int a = x + dx[i], b = y + dy[i];
            if(a >= 0 && a < row && b >= 0 && b < col && !st[a][b]){
                dfs(k, a, b, row, col, st);
            }
         }

    }
};