地毯（暴力+差分两种方法）

题目描述

在 nx n 的格子上有 m 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 n,m。意义如题所述。

接下来 m 行，每行两个坐标 (x_1,y_1) 和 (x_2,y_2)，代表一块地毯，左上角是 (x_1,y_1)，右下角是 (x_2,y_2)。

输出格式

输出 n行，每行n 个正整数。

第 i 行第 j 列的正整数表示 (i,j) 这个格子被多少个地毯覆盖。

样例 #1

样例输入 #1
5 3
2 2 3 3
3 3 5 5
1 2 1 4

样例输出 #1
0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

提示

样例解释

覆盖第一个地毯后：

覆盖第一、二个地毯后：

覆盖所有地毯后：

数据范围

对于 20% 的数据，有 n<= 50，m<= 100。

对于 100% 的数据，有 n,m<= 1000。

第一种方法：暴力做法。这道题的数据范围很小，所以暴力也可以过所有样例。

代码比较简单就不多讲了。

#include <iostream>
#include <algorithm>
using namespace std;const int N = 100010;
int q[N][N]; // 定义一个二维数组来记录操作结果int main()
{int n, m;cin >> n >> m; // 输入n和m，分别表示矩阵的大小和操作的次数// 进行m次操作for (int i = 0; i < m; i++){int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2; // 输入操作的左上角和右下角坐标// 针对操作的区域，进行累加操作for (int j = x1; j <= x2; j++){for (int k = y1; k <= y2; k++){q[j][k]++; // 将区域内的每个元素增加1}}}// 输出操作后的结果for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cout << q[i][j] << " "; // 输出每个位置的操作结果}cout << endl;}return 0;
}

第二种方法：差分。

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1010;
int q[N][N]; // 定义一个二维数组来记录操作结果int main()
{int n, m;cin >> n >> m; // 输入n和m，分别表示矩阵的大小和操作的次数// 进行m次操作for (int i = 0; i < m; i++){int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2; // 输入操作的左上角和右下角坐标// 更新操作for (int j = x1; j <= x2; j++){q[j][y1]++;       // 在该列上加1q[j][y2 + 1]--;   // 在该列的下一行减1，用于区分操作的范围}}// 根据更新操作，计算每个位置的最终值for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){q[i][j] += q[i][j - 1]; // 当前位置的值等于前一列的值加上当前位置的值cout << q[i][j] << " "; // 输出每个位置的最终结果}cout << endl;}return 0;
}