题目描述

地上有一个 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。

算法

(BFS)

1. 这次被res ++的位置绊倒了，位置放错了，应该在auto t = q.front()的后面紧跟着放，因为自己也算是1个格子，我一开始放到了for(i < 4)的里面。
2. 多写了一个gogo()函数，d[][]用来表示该节点是否走过。

时间复杂度

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

C++ 代码

class Solution {
public:
    int k;
    int d[110][110];
    typedef pair<int, int> PII;
    int n, m;

    int gogo(PII p)
    {
        int ans = 0;
        while(p.first)
        {
            ans += p.first % 10;
            p.first /= 10;
        }

        while(p.second)
        {
            ans += p.second % 10;
            p.second /= 10;
        }

        return ans;
    }

    int bfs(PII start)
    {
        memset(d, -1, sizeof d);
        queue<PII> q;
        q.push(start);
        d[start.first][start.second] = 0;

        int res = 0;

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

            res ++;
            for(int i = 0; i < 4; i ++)
            {
                int a = t.first + dx[i], b = t.second + dy[i];
                if(a >= 0 && a < n && b >= 0 && b < m)
                {
                    if(d[a][b] == -1 && gogo(make_pair(a, b)) <= k)
                    {
                        d[a][b] = d[t.first][t.second] + 1;
                        q.push({a, b});
                    }
                }
            }
        }

        return res;
    }

    int movingCount(int threshold, int rows, int cols)
    {
        if(!rows || !cols) return 0;
        n = rows;
        m = cols;
        k = threshold;
        PII start = {0, 0};
        return bfs(start);
    }
};