题目描述

地上有一个 $m$ 行和 $n$ 列的方格，横纵坐标范围分别是 $0∼m−1$ 和 $0∼n−1$。
一个机器人从坐标 $(0,0)$ 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 $k$ 的格子。
请问该机器人能够达到多少个格子？

注意

$0\leq m\leq 50$
$0\leq n\leq 50$
$0\leq k\leq 100$

样例1

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

输出：20

样例2

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

输出：1484

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

这是一道非常模板的广搜题，基本把模板套一下就行了，思路就是从$(0,0)$开始，不停地往四个方向拓展（当然不能从复走啦！），如果满足数位和$\leq k$，就把统计的变量$+1$。

代码

class Solution {
public:

    int res = 1;//要把(0,0)点也统计上去
    int b[55][55] = {0};

    struct node 
    {
        int x, y;
    }q[2505];

    //计算数位和
    int sum(int x)
    {
        int y = 0;
        while (x != 0)
        {
            y += x % 10;
            x /= 10;
        }
        return y;
    }

    //板子
    void bfs(int k, int n, int m)
    {
        int head = 0, tail = 1;
        q[1] = {0, 0};
        b[0][0] = 1;//第一个点一定要设为一，否则会凭空多出来一个
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};//方向数组
        while (head < tail)
        {
            head ++;
            for (int i = 0; i < 4; i ++)
            {
                int x = q[head].x + dx[i];
                int y = q[head].y + dy[i];
                if (x >= 0 && x < n && y >= 0 && y < m && b[x][y] == 0 && sum(x) + sum(y) <= k)//满足条件
                {
                    tail ++;
                    q[tail] = {x, y};
                    b[x][y] = 1;
                    res ++;
                }
            }
        }
    }

    int movingCount(int threshold, int rows, int cols)
    {
        if (rows == 0 || cols == 0) return 0;//特判，否则会WA
        bfs(threshold, rows, cols);
        return res;
    }
};

好了，这就是这篇题解的所有内容，喜欢的话，就给可爱的男孩子一个小小的赞吧，Thanks♪(･ω･)ﾉ！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$