矩形覆盖与清除问题

题目描述

平面上有一个2010×2010的网格，每个格子初始状态为0。有多次矩形操作，每次操作给出一个矩形的左下角坐标(X1,Y1)和右上角坐标(X2,Y2)，要求将该矩形区域内的所有格子标记为1（覆盖）或0（清除）。操作完成后，求网格中值为1的格子数量，即未被覆盖的面积。

解题思路

1. 坐标平移：输入坐标可能为负数，通过加1000平移至非负范围（0~2000），避免数组越界。
2. 二维数组标记：使用bool a[N][N]记录每个格子状态，初始化为0。
3. 矩形操作处理：根据每次输入的矩形坐标，遍历平移后的区域并标记为1（覆盖）或0（清除）。
4. 结果统计：遍历整个数组，统计值为1的格子数量并输出。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
bool a[N][N]; // 网格标记数组，0表示未覆盖，1表示覆盖

int main() {
    memset(a, 0, sizeof(a)); // 初始化网格为未覆盖状态
    
    // 第一次矩形覆盖操作
    int X1, Y1, X2, Y2;
    cin >> X1 >> Y1 >> X2 >> Y2;
    for (int i = X1 + 1000; i < X2 + 1000; ++i) // x坐标平移后遍历
        for (int j = Y1 + 1000; j < Y2 + 1000; ++j) // y坐标平移后遍历
            a[i][j] = 1; // 标记为覆盖
    
    // 第二次矩形覆盖操作
    cin >> X1 >> Y1 >> X2 >> Y2;
    for (int i = X1 + 1000; i < X2 + 1000; ++i)
        for (int j = Y1 + 1000; j < Y2 + 1000; ++j)
            a[i][j] = 1;
    
    // 第三次矩形清除操作
    cin >> X1 >> Y1 >> X2 >> Y2;
    for (int i = X1 + 1000; i < X2 + 1000; ++i)
        for (int j = Y1 + 1000; j < Y2 + 1000; ++j)
            a[i][j] = 0; // 标记为清除（未覆盖）
    
    // 统计覆盖的格子数量
    int ans = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            if (a[i][j]) ans++;
    
    cout << ans << endl;
    return 0;
}

注意事项

1. 坐标平移：输入坐标加1000后范围为0~2000，确保数组a（2010×2010）无越界访问。
2. 边界处理：循环条件用<而非<=，因矩形区域实际为[X1+1000, X2+1000)，符合“标记点”逻辑。
3. 操作优先级：后一次操作会覆盖前一次重叠区域，如第三次清除操作覆盖前两次重叠部分。

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
bool a[N][N];//m为该平面直角坐标系，ans为没有被覆盖的面积
int main()
{
    memset(a,0,sizeof(a));
    int X1,Y1,X2,Y2;
    cin>>X1>>Y1>>X2>>Y2;
    for(int i=X1+1000;i<X2+1000;i++)//x坐标 (注意此处是 < 而不是 <= ,因为标记的是点)
        for(int j=Y1+1000;j<Y2+1000;j++){//y坐标
            a[i][j]=1;
        }
    cin>>X1>>Y1>>X2>>Y2;
    for(int i=X1+1000;i<X2+1000;i++)//x坐标 (注意此处是 < 而不是 <= ,因为标记的是点)
        for(int j=Y1+1000;j<Y2+1000;j++){//y坐标
            a[i][j]=1;
        }
    cin>>X1>>Y1>>X2>>Y2;
    for(int i=X1+1000;i<X2+1000;i++)//x坐标 (注意此处是 < 而不是 <= ,因为标记的是点)
        for(int j=Y1+1000;j<Y2+1000;j++){//y坐标
            a[i][j]=0;
        }
    int ans=0;
    for(int i=0;i<=2000;i++)
        for(int j=0;j<=2000;j++){
            if(a[i][j])ans++;
        }
    cout<<ans;
    return 0;
}