G4015 [GESP202503 四级] 荒地开垦 题解

知识点：二维数组、贡献计数、枚举优化。

解题思路

对每格检查自身及上下左右五个位置的#数量：0个时计入原有可用格；恰1个时给唯一#所在位置记一份清除收益，最后加最大收益。

为什么正确

清掉一个#只能使原先仅被它阻碍的格子新变可用，其他格子状态不变，因此逐格贡献可相加。

易错点

计邻域时包括中心格；有两个及以上#阻碍的格子不能因清掉一个而贡献收益。

复杂度

时间O(nm)，空间O(nm)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<string>a(n);
    for(auto &s:a)cin>>s;
    vector<vector<int>>gain(n,vector<int>(m));
    int base=0;
    int dx[]= {
        0,1,-1,0,0
    }
    ,dy[]= {
        0,0,0,1,-1
    }
    ;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++) {
        int c=0,x=-1,y=-1;
        for(int k=0;k<5;k++) {
            int u=i+dx[k],v=j+dy[k];
            if(u>=0&&u<n&&v>=0&&v<m&&a[u][v]=='#') {
                c++;
                x=u;
                y=v;
            }
        }
        if(c==0)base++;
        else if(c==1)gain[x][y]++;
    }
    int best=0;
    for(auto row:gain)for(int x:row)best=max(best,x);
    cout<<base+best;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。