题意:给定一个矩阵,可以相邻的行或列交换一个元素。首尾也算相邻。最小交换多少次。可以使每行梅列的1的个数相同。或每一行的1的数量一样多。或每一列一样多。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
const int N = 1009;
const int INF = 0x3f3f3f3f;
char a[N][N];
int row[N],col[N],re[N];
int n,m,s;
int get(int nn,int f,int t)
{
int l=f,k=0;
int ret = 0;
while(k<nn)
{
if(re[l]==t)
{
}else if(re[l]>t)
{
ret+=re[l]-t;
re[(l+1)%nn] += re[l]-t;
}else
{
ret+=t-re[l];
re[(l+1)%nn] -= t-re[l];
}
l=(l+1)%nn;
k++;
}
return ret;
}
void solve()
{
int k = 0,ans = 0;
if(s%n==0)
{
k|=1;
int tmp = INF;
for(int i=0;i<n;i++)
memcpy(re,row,sizeof(row)),tmp = min(tmp,get(n,i,s/n));
ans +=tmp;
// cout<<tmp<<" - ";
}
//cout<<k<<endl;
if(s%m==0)
{
k|=2;
int tmp = INF;
for(int i=0;i<m;i++)
memcpy(re,col,sizeof(col)),tmp = min(tmp,get(m,i,s/m));
ans+=tmp;
//cout<<tmp<<endl;
}
//cout<<"K= "<<k<<endl;
if(k==3)
printf("both %d\n",ans);
else if(k==1)
printf("row %d\n",ans);
else if(k==2)
printf("column %d\n",ans);
else printf("impossible\n");
}
int main()
{
freopen("in.txt","r",stdin);
int cas,T= 1;
scanf("%d",&cas);
while(cas--)
{
memset(row,0,sizeof(row));
memset(col,0,sizeof(col));s=0;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%s",a[i]);
for(int j=0;j<m;j++)
if(a[i][j]=='1')
row[i]++,col[j]++,s++;
}
printf("Case %d: ",T++);
solve();
}
return 0;
}