描述
给你一个大小为n×m的矩阵a, a(i, j)代表矩阵的第i行第j列元素(1≤i≤n,1≤j≤m)
每次你可以选择该矩阵的第x(1≤x≤n)行, 第y(1≤y≤m)列的元素a(x, y), 进行如下任意一种操作
注意: 如果你选择的x = 1, 则不能进行操作1; 如果你选择的y = 1, 则不能进行操作2
操作1: (x ≠ 1)
计算: c = a(x, 1) + a(x, 2) + ⋯ + a(x, y−1) + a(x, y)
a(x−1, y) = a(x−1, y) + c
a(x, y) = a(x, y) − 2×c
x≠n情况下: a(x+1, y) = a(x+1, y) + c
y≠m情况下: a(x−1, y+1) = a(x−1, y+1) − c
y≠m情况下: a(x, y+1) = a(x, y+1) + 2×c
x≠n且y≠m情况下: a(x+1, y+1) = a(x+1, y+1) − c
操作2: (y ≠ 1)
计算: c = a(1, y) + a(2, y) + ⋯ + a(x−1, y) + a(x, y)
a(x, y−1) = a(x, y−1) + c
a(x, y) = a(x, y) − 2×c
y≠m情况下: a(x, y+1) = a(x, y+1) + c
x≠n情况下: a(x+1, y−1) = a(x+1, y−1) − c
x≠n情况下: a(x+1, y) = a(x+1, y) + 2×c
x≠n且y≠m情况下: a(x+1, y+1) = a(x+1, y+1) − c
现在有一个大小n×m的目标矩阵b, 你可以进行无限次上述操作, 我们想知道能否从矩阵a通过上述操作变换为矩阵b?
格式
输入格式
第一行包含2个正整数n, m (1≤n, m≤100), 表示矩阵的大小
第二行到第n+1行, 第i+1行包含m个整数, 表示矩阵a的第i行的m个元素, −≤a(i, j)≤
第n+2行到第2n+1行, 第i+n+1行包含m个整数, 表示矩阵b的第i行的m个元素, −≤b(i, j)≤
输出格式
如果存在一种操作方式, 矩阵a能够变换为矩阵b, 输出"Yes"(不包含引号), 否则输出"No"(不包含引号)
样例
输入样例
3 3 1 2 3 4 5 6 7 8 9 1 4 1 11 -13 17 0 24 0
输出样例
Yes
限制
时间限制: 1000 ms
内存限制: 65536 KB
提示
对于样例1, 初始矩阵a为:
1 2 3
4 5 6
7 8 9
先选择a(2, 2)进行操作2, 矩阵变为:
1 2 3
11 −9 13
0 22 2
再选择a(2, 2)进行操作1, 矩阵变为:
1 4 1
11 −13 17
0 24 0
最终得到目标矩阵b
提示：二维前缀和
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x7fffffff
int n, m; //n是行 m是列
int a[110][110], b[110][110];
//int f1[110][110]={0},f2[110][110]={0};
//int flag[110][110]={0}; //0 相等
int cx, cy;
//int xx=2,yy=2;
void check();
int res = 0;
int dp[110][110];
int dp2[110][110];
queue<int> qx;
queue<int> qy;
void countx(int x, int y) { //计算x行的值
cx = 0;
for (int i = 1; i <= y; i++) {
cx += a[x][i];
}
}
void county(int x, int y) {
cy = 0;
for (int i = 1; i <= x; i++) {
cy += a[i][y];
}
}
void op1(int x, int y) { //操作1模拟 无实际用处
a[x - 1][y] += cx;
a[x][y] -= 2 * cx;
if (x != n) {
a[x + 1][y] += cx;
}
if (y != m) {
a[x - 1][y + 1] -= cx;
a[x][y + 1] += 2 * cx;
}
if (x != n && y != m) {
a[x + 1][y + 1] -= cx;
}
}
void op2(int x, int y) { //操作2模拟
a[x][y - 1] += cy;
a[x][y] -= 2 * cy;
if (y != m) {
a[x][y + 1] += cy;
}
if (x != n) {
a[x + 1][y - 1] -= cy;
a[x + 1][y] += 2 * cy;
}
if (x != n && y != m) {
a[x + 1][y + 1] -= cy;
}
}
void solve() {
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
countx(x, y); county(x, y);
if (a[x - 1][y] + cx == b[x - 1][y]) {
op1(x, y);
// cout<<"op1 "<<x<<","<<y<<endl;
check();
}
else if (a[x][y - 1] + cy == b[x][y - 1]) {
op2(x, y);
// cout<<"op2 "<<x<<","<<y<<endl;
check();
}
else {
// cout<<"No";
return;
}
}
void check() {
int flag = 0;
int i, j;
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
if (a[i][j] != b[i][j]) {
flag = 1;
break;
}
}
if (flag) {
if (i != n) {
qx.push(i + 1);
qy.push(j);
// cout << i+1 << " " << j << endl;
solve();
}
if (j != m) {
qx.push(i);
qy.push(j + 1);
// cout << i << " " << j+1 << endl;
solve();
}
// if (j != m && i!=n) {
// qx.push(i + 1);
// qy.push(j + 1);
// cout << i+1 << " " << j+1 << endl;
// solve();
// }
break;
}
}
flag = 0;
if (i == n + 1 && j == m + 1) {
res = 1;
}
for (j = 1; j <= m; j++) {
if (res)break;
for (i = 1; i <= n; i++) {
if (a[i][j] != b[i][j]) {
flag = 1;
break;
}
}
if (flag) {
if (i != n) {
qx.push(i + 1);
qy.push(j);
// cout << i+1 << " " << j << endl;
solve();
}
if (j != m) {
qx.push(i);
qy.push(j + 1);
// cout << i << " " << j+1 << endl;
solve();
}
// if (j != m && i!=n) {
// qx.push(i + 1);
// qy.push(j + 1);
// cout << i+1 << " " << j+1 << endl;
// solve();
// }
break;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> b[i][j];
// if(a[i][j]!=b[i][j])flag[i][j]=1;
}
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)//预处理一波
for(int j=1;j<=m;j++)
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+a[i][j];
// for(int i=1;i<=k;i++){ //查询
// int x1,x2,y1,y2;
// cin >>x1>>y1>>x2>>y2;
// cout <<(dp[x2][y2]+dp[x1-1][y1-1]-dp[x1-1][y2]-dp[x2][y1-1])<<endl;//O（1）查询
// }
ll suma=0,sumb=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
suma+=dp[i][j];
}
memset(dp2,0,sizeof(dp2));
for(int i=1;i<=n;i++)//预处理一波
for(int j=1;j<=m;j++)
dp2[i][j]=dp2[i-1][j]+dp2[i][j-1]-dp2[i-1][j-1]+b[i][j];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
sumb+=dp2[i][j];
}
// int xx=2,yy=2;
// solve(2,2);
// check();
if (suma==sumb) {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}