[acwing#24]机器人的运动范围(BFS-DFS)

题目来源:https://www.acwing.com/problem/content/22/

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

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

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

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

样例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<=m<=50
0<=n<=50
0<=k<=100


搜索的模板题,用一个bool数组g[][]维护方格能否到达,方格可以到达的条件是:在范围内、坐标的数位之和小于等于k。可以先对坐标数位之和进行预处理,使用bfs或dfs进行遍历,用ans表示可以进入的方格数量,每进入一个,ans++。

#include <bits/stdc++.h>
using namespace std;
bool g[60][60];
int n, m, k, ans;
typedef pair<int, int> P;
int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int main(){
    cin >> k >> m >> n;
    memset(g, false, sizeof(g)); 
    for(int i=0; i<m; i++)
        for(int j=0; j<n; j++){
            g[i][j] = true;
            int x = i, y = j;
            int t = 0;
            while(x){
                t += x%10;
                x /= 10;
            }
            while(y){
                t += y%10;
                y /= 10;
            }
            if(t>k)  // 预处理
                g[i][j] = false;
        }
    queue<P> q;
    q.push((P){0, 0});
    g[0][0] = false;
    ans = 1;
    while(!q.empty()){
        P u = q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int tx = u.first+d[i][0];
            int ty = u.second+d[i][1];
            if(g[tx][ty] && tx>=0 && tx<m && ty>=0 && ty<n){
                ans++;
                g[tx][ty] = false;
                q.push((P){tx, ty});
            }
        }
    }
    cout << ans;
    return 0;
}

[acwing#24]机器人的运动范围(BFS-DFS)

上一篇:jQuery学习之路(四)之过滤选择器


下一篇:PHP 生成图片缩略图函数