首先 \(1\) 的总个数不能被 \(n\) 整除时无解。
否则一定有解（因为每一列上的 \(1\) 的位置都可以随意变动，故实际上相当于可以随便放）。为了步数最少，一定是用缺少 \(1\) 行的 \(0\) 与过多 \(1\) 行的 \(1\) 交换，这样能同时使两行更接近答案。实现时先枚举列，再根据每行的情况找出上面两种行，并一一配对交换即可。时间复杂度 \(O(\sum nm)\)。
#include<iostream>
#include<cstdio>
#include<vector>
#define N 200010
using namespace std;
int n,m,cnt[N],cnt0;
vector<int> G[N],a,b;
int ans,ansx[N*10],ansy[N*10],ansz[N*10];
void solve(){cnt0=0;cin>>n>>m;for(int i=1;i<=n;i++)G[i].clear();for(int i=1;i<=n;i++){G[i].push_back(0);cnt[i]=0;for(int j=1;j<=m;j++){G[i].push_back(0);cin>>G[i][j];cnt0+=G[i][j];cnt[i]+=G[i][j];}}if(cnt0%n){cout<<-1<<'\n';return;}cnt0/=n;ans=0;for(int j=1;j<=m;j++){a.clear();b.clear();for(int i=1;i<=n;i++){if(cnt[i]<cnt0&&!G[i][j])a.push_back(i);if(cnt[i]>cnt0&&G[i][j])b.push_back(i);}for(int i=0;i<min(a.size(),b.size());i++){ans++;ansx[ans]=a[i],ansy[ans]=b[i],ansz[ans]=j;cnt[a[i]]++,cnt[b[i]]--;}}cout<<ans<<'\n';for(int i=1;i<=ans;i++)cout<<ansx[i]<<' '<<ansy[i]<<' '<<ansz[i]<<'\n';return;
}
int main(){int T;cin>>T;while(T--)solve();return 0;
}