我们注意到对如图倒三角形上的所有点操作都会影响到目标点。
那么我们可以维护两个前缀和，第一个前缀和表示如下的点是否操作
第二个前缀和表示这些点是否操作
这样我们求出了前缀和之后，将两个前缀和异或一下就知道该点是否要操作了。
#include<bits/stdc++.h>
using namespace std;
int t,n,b[2][3005],c[2][3005],ans;
char a[3005][3005];
int main(){
cin>>t;
while(t--){
cin>>n;
ans=0;
for(int i=1;i<=n;i++)cin>>(a[i]+1);
for(int j=0;j<=n+1;j++)b[0][j]=b[1][j]=c[0][j]=c[1][j]=0;
for(int i=1;i<=n;i++){
int sum=0;
for(int j=1;j<=n;j++){
b[1][j]=b[0][j+1]^sum;
c[1][j]=c[0][j-1]^sum;
int nowans=b[1][j]^c[1][j-1];
if(nowans^(a[i][j]-'0'))ans++,sum^=1,b[1][j]^=1,c[1][j]^=1;
}
b[1][n+1]=b[1][n];
for(int j=1;j<=n+1;j++)b[0][j]=b[1][j],c[0][j]=c[1][j];
}
cout<<ans<<"\n";
}
return 0;
}