【Atcoder】【ABC383】B.Humidifier2题解

题目传送门：B - Humidifier 2

题目大意

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

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

与加湿器的曼哈顿距离

不大于的空格可以被加湿

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

（保证至少有两个空地）

思路

还是首先看到数据范围

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

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

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

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;
}

总结

也是比较基础的一题，没什么好说的

上述代码时间复杂度，怎么说呢

六重循环有点丑，大家也可以想想怎么优化

最后，内容创作不易，如果你喜欢就请点个收藏点个赞

我的主页里也有更多竞赛真题，感谢大家的支持！

原文地址：https://blog.csdn.net/weixin_52398991/article/details/144327774

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！