求解要用c++求一次过

Question

题目描述
在 n×n
的格子上有 m
个地毯。

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

格子的左上角坐标为（1，1）。

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

接下来 m
行，每行两个坐标 (x1,y1)
和 (x2,y2)
，代表一块地毯，左上角是 (x1,y1)
，右下角是 (x2,y2)
。

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

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

样例
输入

5 3
2 2 3 3
3 3 5 5
1 2 1 4
输出

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
提示
对于 100% 的数据，有 n,m≤1000
时间限制
1000MS
空间限制
128MB
用c++

Answer 1

YYX_YYJ 向您问好~
当前：离线❤️

解题思路：
暴力方法解决：

   这题的解题思路还是很清晰的，
既然地毯的范围都告诉你了，
那有一个很简单且暴力的方法就是每次给定地毯的大小之后使范围内数组的值全部加一，
经过m次这样的操作之后，
再把数组中的值打印出来即可，
但是如果这样做的话，每次使地毯内的值加一的时间复杂度是o(n^2)，
那么整个程序的时间复杂度就是o(mn^2+n^2)
，题目的数据范围是n，m<=1000，那如果是<=10000，
  那么这么大的时间复杂度就显然不能满足所需，那么有没有更好的方法呢？
答案肯定是有的，这里附上暴力算法的代码。

请查看正确代码：

#include<stdio.h>
int grid[1002][1002];
//使用全局变量定义数组是因为1002*1002所占用的空间太大，定义为局部变量容易爆栈
void cover( int x1, int y1, int x2, int y2)
{
    int i = 0;
    int j = 0;
    for (i = x1; i <= x2; i++)
    {
        for (j = y1 ; j <= y2; j++)
            ++grid[i][j];
    }
}
 
int main()
{
    int n = 0,m = 0;
    scanf("%d %d", &n,&m);
    int  i = 0,j = 0;
    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    for (i = 0; i < m; i++)
    {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        cover(x1, y1, x2, y2);
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            printf("%d ", grid[i][j]);
        }
        printf("\n");
    }
    return 0;
}