题目描述
输入一个n行m列的整数矩阵,再输入q个操作,每个操作包含五个整数x1, y1, x2, y2, c,其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上c。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数n,m,q。
接下来n行,每行包含m个整数,表示整数矩阵。
接下来q行,每行包含5个整数x1, y1, x2, y2, c,表示一个操作。
输出格式
共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。
数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000
输入样例:
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
输出样例:
2 3 4 1
4 3 4 1
2 2 2 2
观众老爷们,如果本思路对您有帮助,求关注一波~~~
思路
一维差分 https://www.acwing.com/solution/content/32498/
有了一维数组做支撑,对于一个插入的数值a[i][j],在构造b数组时候,需要在(i,j,i,j)插入数a[i][j]
构造insert(x1, y1, x2, y2, x)成了主要对象
来自网络图片
可以很明显的推出,插入的公式
b[x1][y1] += c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y1] -= c;
b[x2 + 1][y2 + 1] += c; //被b[x1][y2 + 1]和b[x2 + 1][y1]重复减去c的区域
二维矩阵计算前缀和看 https://www.acwing.com/solution/content/32482/
计算公式 b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + b[i][j];
```
void insert(int x1, int y1, int x2, int y2, int c){
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
```
java(代码臃肿,Scanner使用超时, 利用BufferedReader 和 BufferedWriter解决)
import java.util.Scanner;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main{
static int n, m, q;
static int N = 1010;
static int[][] a = new int[N][N], b = new int[N][N];
public static void insert(int x1, int y1, int x2, int y2, int c){
b[x1][y1] += c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y1] -= c;
b[x2 + 1][y2 + 1] += c;
}
public static void main(String[] args) throws IOException{
// Scanner读取超时
// Scanner sc = new Scanner(System.in);
// n = sc.nextInt();
// m = sc.nextInt();
// q = sc.nextInt();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
q = Integer.parseInt(s[2]);
for(int i = 1; i <= n; i ++){
String[] in = br.readLine().split(" ");
for(int j = 1; j <= m; j ++){
// a[i][j] = sc.nextInt();
a[i][j] = Integer.parseInt(in[j - 1]);
}
}
//生成初始化b[i],可以和上面合并
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
insert(i, j, i, j, a[i][j]);
}
}
//按区间进行 + c
while(q -- != 0){
// int x1, y1, x2, y2, c;
// x1 = sc.nextInt();
// y1 = sc.nextInt();
// x2 = sc.nextInt();
// y2 = sc.nextInt();
// c = sc.nextInt();
String[] info = br.readLine().split(" ");
int x1 = Integer.parseInt(info[0]);
int y1 = Integer.parseInt(info[1]);
int x2 = Integer.parseInt(info[2]);
int y2 = Integer.parseInt(info[3]);
int c = Integer.parseInt(info[4]);
insert(x1, y1, x2, y2, c);
}
//前缀和
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + b[i][j];
}
}
//可以和上面合并
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
//System.out.print(b[i][j] + " "); //超时
bw.write(b[i][j] + " ");
}
//System.out.println(); //超时
bw.write("\n");
}
bw.flush();
br.close();
bw.close();
}
}
python
a = [[0] * 1010 for i in range(1010)]
b = [[0] * 1010 for i in range(1010)]
def insert(x1, y1, x2, y2, c):
b[x1][y1] += c
b[x1][y2 + 1] -= c
b[x2 + 1][y1] -= c
b[x2 + 1][y2 + 1] += c
def main():
global a
global b
n, m, q = list(map(int, input().split()))
for i in range(n):
rows = list(map(int, input().split()))
for j in range(m):
a[i + 1][j + 1] = rows[j]
for i in range(n):
for j in range(m):
insert(i + 1, j + 1, i + 1, j + 1, a[i + 1][j + 1])
while(q != 0):
x1, y1, x2, y2, c = list(map(int, input().split()))
insert(x1, y1, x2, y2, c)
q -= 1
for i in range(n):
for j in range(m):
b[i + 1][j + 1] = b[i][j + 1] + b[i + 1][j] - b[i][j] + b[i + 1][j + 1]
for i in range(n):
for j in range(m):
print(b[i + 1][j + 1], end=" ")
print()
main()
c++
#include<iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c){
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
int main(){
cin >> n >> m >> q;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
scanf("%d", &a[i][j]);
}
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
insert(i, j, i, j, a[i][j]);
}
}
while(q --){
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
insert(x1, y1, x2, y2, c);
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + b[i][j];
}
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
printf("%d ", b[i][j]);
}
puts("");
}
}