P1696 [USACO18JAN] Blocked Billboard II B 题解

qw1234321 · 2024-01-08 16:47:24 · 题解

一眼，暴力。

坐标范围挺小，可以直接暴力求解，把割草机广告坐标全染色为 1，饲料广告设染色为 2。

然后暴力寻找未被盖到的坐标的最大最小值。

最后直接用暴力求到的左上角和右下角两个点的坐标计算面积即可。

贴个部分代码：

const int N = 2e3 + 10, INF = 1e9;
int s[2][4];
int g[N][N];
//初始化，最小值初始化为正无穷,最大值初始化为负无穷 
int x1 = INF, y1 = INF, x2 = -INF, y2 = -INF;

int main(){
    for (int i = 0; i < 2; i++) for (int j = 0; j < 4; j++) cin >> s[i][j];
    for (int k = 0; k < 2; k++){
        for (int i = s[k][0]; i < s[k][2]; i++){
            for (int j = s[k][1]; j < s[k][3]; j++){
                g[i][j] = k + 1;//把割草机广告坐标全染色为 1，饲料广告染色为 2
            }
        }
    }
    //寻找未被盖到的坐标的最大最小值
    for (int i = s[0][0]; i < s[0][2]; i++){
        for (int j = s[0][1]; j < s[0][3]; j++){
            if (g[i][j] == 1){
                x1 = min(x1, i);
                x2 = max(x2, i);
                y1 = min(y1, j);
                y2 = max(y2, j);
            }
        }  
    }
    //计算面积 
    if (x2 >= x1 && y2 >= y1) cout << (x2 - x1 + 1) * (y2 - y1 + 1);
    else cout << 0;

RE 撒花！

那究竟是为什么 RE 呢？发现在用到的数组下标 i 也许是负数，j 同理。所以吧 i,j 同时加上 1000 就行啦！

这样 AC 代码就很简单了，请读者自行在原 RE 的代码上改改，思考思考。(好像都不用思考耶)