题目描述

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

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

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

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

样例

输入：k=7, m=4, n=5

输出：20

注意：

• 0<=m<=50
• 0<=n<=50
• 0<=k<=100

算法1

(BFS) $O(nm)$

这是一道典型的宽度优先搜索问题，从 (0, 0) 开始遍历，每次朝着上右下左四个方向运动
需要注意满足的条件：

1. 没有被遍历过，可以用二维 bool 数组标记当前点有没有被访问过
2. 下标不能越界
3. 数位之和不超过 k

时间复杂度

每个格子最多会入队一次出队一次，所以时间复杂度不会超过格子个数
最坏情况下会遍历方格中所有点，所以时间复杂度是 $O(nm)$

C++ 代码

class Solution {
public:
    int get_single_sum(int n)
    {
        int res = 0;
        while (n) res += n % 10, n /= 10;
        return res;
    }

    int get_sum(int x, int y)
    {
        return get_single_sum(x) + get_single_sum(y);
    }

    int movingCount(int threshold, int rows, int cols)
    {
        if (!rows || !cols) return 0;

        int res = 0;
        queue<pair<int, int>> q;
        vector<vector<bool>> st(rows, vector<bool>(cols, false));
        q.push({0, 0});

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        while (q.size())
        {
            auto t = q.front();
            q.pop();

            if (get_sum(t.first, t.second) > threshold || st[t.first][t.second]) continue;
            st[t.first][t.second] = true;
            res ++ ;

            for (int i = 0; i < 4; i ++ )
            {
                int a = t.first + dx[i], b = t.second + dy[i];
                if (a >= 0 && a < rows && b >= 0 && b < cols)
                    q.push({a, b});
            }
        }

        return res;
    }
};