返回题解分享
讨论 / 题解分享/ 帖子详情

二维差分 - 题解

/*
思路
    思路一:
        1.二维数组+循环操作+双变量
        2.循环操作: x1 ,y1 ==》 x2 , y2 
        [1,2] ==>[2,4] y1--y2  x1--x2
    思路二: 
        1.两个数组 原数组 差分数组
        2.循环操作---输入数据
        3.循环操作---得到差分数组
        4.循环操作---处理差分数组a-c --- (b+1)-c     
        5.循环操作---处理后的原数组(前缀和数组)
        6.循环操作---输出处理后的原数组 
*/
/*
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,m,q;
    cin >> n >> m >> q;

    //二维数组定义接收数据
    vector<vector<int>> arr(n , vector<int>(m));
    for ( int i = 0; i < n; i++ ) {
        for ( int j = 0; j < m; j++ ) {
            cin >> arr[i][j];
        }
    }
    //循环操作
    for ( int i = 0; i < q; i++ ) {
        int x1,y1,x2,y2,c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        for ( int j = x1-1; j <= x2-1; j++ ) {
            for ( int k = y1-1; k <= y2-1; k++ ){
                arr[j][k] = arr[j][k] + c;
            }
        }
    }
    //输出
    for ( int i = 0; i < n; i++ ) {
        for ( int j = 0; j < m; j++ ) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
*/

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m, n, q;
    cin >> m >> n >> q;

    // 定义原数组和差分数组,大小为 (m+2)×(n+2),多留一圈边界
    vector<vector<int>> arr(m + 2, vector<int>(n + 2, 0));
    vector<vector<int>> diff(m + 2, vector<int>(n + 2, 0));

    // 接收原数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }

    // 初始化差分数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            diff[i][j] = arr[i][j];
            if (i > 1) diff[i][j] -= arr[i - 1][j];
            if (j > 1) diff[i][j] -= arr[i][j - 1];
            if (i > 1 && j > 1) diff[i][j] += arr[i - 1][j - 1];
        }
    }

    // 处理差分数组
    for (int i = 1; i <= q; i++) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        diff[x1][y1] += c;
        diff[x1][y2 + 1] -= c;
        diff[x2 + 1][y1] -= c;
        diff[x2 + 1][y2 + 1] += c;
    }

    // 恢复原数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 累加差分数组
            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
            // 更新原数组
            arr[i][j] = diff[i][j];
        }
    }

    // 输出结果数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}
0 回复 0 转发 0 喜欢 5 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!