首先把式子拆一下，可以知道 \(x-i \ge |y-j|\) 等价于 \(x-y \ge i-j\) 和 \(x+y \ge i+j\)，注意到每次操作 \((i,j)\)，影响到的点 \((x,y)\) 均要满足 \(x>i\)，那么我们每次就必须要按照从上往下的顺序进行，否则上面的点无法影响到，即从第一行开始操作。
又注意到对于 \((i,j)\) 如果执行了两次操作相当于没有执行操作，因此对于 \((i,j)\) 我们最多执行一次操作。
所以得出了一种贪心求法：从第一行往下，每次碰到不是 \(0\) 的就修改，可以证明一定步数最小。时间复杂度 \(O(n^4)\) 无法承受。
我们考虑优化修改的过程，注意到我们修改的时候区域是连续的，类似一个三角形的形状，所以我们可以类比二维前缀和与二维差分，维护两条直线来进行优化，分别是斜率为 \(1\) 和斜率为 \(-1\) 的两条直线。
我们用 \(b\) 数组维护斜率为 \(-1\) 的直线，用 \(c\) 数组维护斜率为 \(1\) 的直线，注意到状态只有 \(\{1,0\}\)，因此我们可以用异或来简便操作。
时间复杂度 \(O(n^2)\)。
#include <cstdio>
int t;
int n;
int a[3005][3005];
int b[3005][3005],c[3005][3005];
void solve() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) scanf("%1d",&a[i][j]);
}
int sum=0,tot=0;//sum表示修改次数，tot辅助于修改
for(int i=1;i<=n;i++) {//从第一行开始，自上而下
for(int j=1;j<=n;j++) {//求出每个格子的状态，要注意边界
a[i][j]^=(sum&1);//前面行的操作对当前行的影响，如果有影响到当前可以改变，如果没有影响到在后面与b，c异或时可以抵消
if(j-2>=1) a[i][j]^=b[i-1][j-2];
if(j+2<=n) a[i][j]^=c[i-1][j+2];
}
for(int j=1;j<=n;j++) {//统计有多少个格子在第i行被执行操作
if(a[i][j]) ++sum;
}
tot=0;
for(int j=1;j<=n;j++) {//下传
tot^=a[i][j];
b[i][j]=b[i-1][j-1]^tot;
}
tot=0;
for(int j=n;j>=1;j--) {//下传，注意边界
tot^=a[i][j];
if(j!=n) c[i][j]=c[i-1][j+1]^tot;
else c[i][j]=tot;
}
}
printf("%d\n",sum);
}
int main() {
scanf("%d",&t);
while(t--) solve();
return 0;
}