题解：AT_abc383_b [ABC383B] Humidifier 2

Jayfeather2012 · 2025-02-04 21:04:16 · 题解

思路

暴力出奇迹~~
暴力枚举万岁~~
观察到 1\leq H \leq10 且 1\leq W \leq10 ，O(n^8) 都不会炸，于是考虑暴力枚举。
先枚举第一个加湿器的位置 (i,j)，再枚举第二个加湿器的位置 (k,l)，接着遍历地板，找出当第一个加湿器的位置为 (i,j)，第二个加湿器的位置为 (k,l) 时加湿的空地数，所有情况取最大值后输出。
时间复杂度 O(n^6)。
具体细节看代码吧！

代码

#include<bits/stdc++.h>
#define ll long long
#define pp pair<int,int>
using namespace std;
int n,m,d,ans;
char a[15][15];
int sum(int xa,int ya,int xb,int yb){
    return abs(xa-xb)+abs(ya-yb);
}
//计算曼哈顿距离 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>d;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)cin>>a[i][j];
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            //枚举第一个加湿器位置 
            if(a[i][j]=='#')continue;
            //不是地板，不继续 
            for(int k=1;k<=n;++k){
                for(int l=1;l<=m;++l){
                    //枚举第二个加湿器位置 
                    if(a[k][l]=='#'||k==i&&l==j)continue;
                    //不是地板，不继续 
                    //两个加湿器位置相等，不继续 
                    int s=0;
                    for(int x=1;x<=n;++x){
                        for(int y=1;y<=m;++y){
                            //遍历地板 
                            if(a[x][y]=='#')continue;
                            //不是地板，不继续 
                            if(sum(i,j,x,y)<=d||sum(k,l,x,y)<=d)++s;
                            //若曼哈顿距离小于d，增加加湿的空地数 
                        }
                    }
                    ans=max(ans,s);//取最大值 
                }
            }
        }
    }
    cout<<ans<<"\n"; 
    return 0;
}