题目描述

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

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

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

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

样例

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

输出：20

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

输出：1484

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

注意

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

算法1

(BFS) $O(nm)$

从 (0, 0) 点开始，每次朝上下左右四个方向扩展新的节点。
扩展时需要注意新的节点需要满足如下条件：
1) 之前没有遍历过，这个可以用个bool数组来判断；
2) 没有走出边界；
3) 横纵坐标的各位数字之和小于 k；
答案就是所有遍历过的合法的节点个数。

时间复杂度

每个节点最多只会入队一次，所以时间复杂度不会超过方格中的节点个数。

最坏情况下会遍历方格中的所有点，所以时间复杂度就是 O(nm)O(nm)。

参考文献

C++ 代码

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

    int get_sum(pair<int, int> p)
    {
        return get_single_sum(p.first) + get_single_sum(p.second);
    }

    int movingCount(int k, int rows, int cols)
    {
        int res = 0;
        if(!rows || !cols) return 0;
        //判重数组  防止走重复的格子  初始化全部为false
        vector<vector<bool>> v(rows, vector<bool>(cols));

        //队列 pair的初始化
        queue<pair<int, int>> q;

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        //从0，0点开始广度搜索
        q.push({0, 0});

        //如果队列大小为0，遍历完毕
        while(q.size())
        {
            //获取队首元素，并弹出
            auto t = q.front();
            //忘记pop，也会死循环
            q.pop();

            //如果不满足条件，遍历下一个点 
            if(get_sum(t) > k || v[t.first][t.second]) continue;
            //如果满足条件res++
            res++;

            //遍历过的点记录为true 容易忘记，忘记写会死循环
            v[t.first][t.second] = true;

            //沿着上下左右四个方向广度遍历
            for(int i=0;i<4;i++)
            {
                int x = t.first + dx[i], y = t.second + dy[i];
                //将满足条件的点，压入队列中
                if(x >= 0 && x < rows && y >=0 && y < cols)
                    q.push({x,y});
            }

        }


        return res;
    }

};