当前位置：首页 > article >正文

【Atcoder】【ABC383】B.Humidifier2题解

article 2025/1/24 22:34:20

题目传送门：B - Humidifier 2

题目大意

给定 $H * W$ 的矩阵和 $D$ ，每个字符可能是 '#' 或 ‘ . ’（分别表示墙和空地）

要求选出两个空地放置加湿器，

与加湿器的曼哈顿距离 $(dis(P_1(x_1,y_1),P_2(x_2,y_2)) = |x_1-x_2| + |y_1 - y_2|)$

不大于 $D$ 的空格可以被加湿

求最多有几个空地可以被加湿

（保证至少有两个空地）

思路

还是首先看到数据范围

$H,W$ 都很小，于是我们就可以尝试这样一个方法：

枚举两个加湿器的位置。对于每个加湿器，判断每个格子能否被加湿

为了方便计算，可以先定义计算两点之间曼哈顿距离的函数：

int dis(int x1, int x2, int y1, int y2){
    return abs(x1-x2) + abs(y1-y2);
}

另外需要注意，对于两个加湿器不能分别计算，因为可能有重合

我这里的方法是直接开一个数组vis来记录的……

程序框架部分就不用多说了，直接上代码：

AC代码

#include<iostream>
#include<cstring>
using namespace std;
#define For(i, j, k) for(int i = j; i <= k; i++)
#define MaxN 15

int n, m, D, ans;
int vis[MaxN][MaxN];
char a[MaxN][MaxN];

int dis(int x1, int y1, int x2, int y2){    //计算曼哈顿距离
    return abs(x1 - x2) + abs(y1 - y2);
}

void count(int i, int j){        //统计哪几个点能被加湿
    For(i2, 1, n){
        For(j2, 1, m){
            if(a[i2][j2] == '.' && dis(i, j, i2, j2) <= D){
                vis[i2][j2] = 1;
            }
        }
    }
    
}

int main()
{
    cin >> n >> m >> D;
    For(i, 1, n){
        For(j, 1, m){
            cin >> a[i][j];
        }
    }
    For(i, 1, n){
        For(j, 1, m){
            For(i2, 1, n){
                For(j2, 1, m){
                    if(a[i][j] == '.' && a[i2][j2] == '.' && !(i == i2 && j == j2)){
                        memset(vis, 0, sizeof(vis));
                        count(i, j); count(i2, j2);        //分别统计
                        int cnt = 0;            //一共能加湿的空格数
                        For(k, 1, n){
                            For(l, 1, m){
                                if(vis[k][l]) cnt++;
                            }
                        }
                        ans = max(ans, cnt);        //答案在所有方案中取最大值
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}