https://contest.xinyoudui.com/contest/318/problem/1625
#include<bits/stdc++.h>
using namespace std;
int n,m,a[400][400],b[400][400],dp[400][400],c[400][3],k[400],cnt,ans[400][400];
void bbdp()
{
memset(dp,0x3f,sizeof dp);
dp[0][0]=0;
for(int i=1;i<=(m+1)/2;i++)
{
for(int j=0;j<=m;j++)
{
dp[i][j]=dp[i-1][j]+c[i][0];
if(j>=1)
dp[i][j]=min(dp[i][j],dp[i-1][j-1]+c[i][1]);
if(j>=2&&(!(m%2==1&&i==(m+1)/2)))
dp[i][j]=min(dp[i][j],dp[i-1][j-2]+c[i][2]);
if(i+1>(m+1)/2)
ans[cnt][j]=min(ans[cnt][j],dp[i][j]);
}
}
}
void dfs(int x)
{
if(x==n+1)
{
int f1=0,f2=0,hi,hk,tt;
memset(c,0,sizeof c);
for(int j=1;j<=m/2;j++)
{
f1=0;
f2=0;
for(int i=1;i<=n/2;i++)
{
hi=(k[i]==1&&a[i][j]!=a[i][m-j+1]);
hk=(k[n-i+1]==1&&a[n-i+1][j]!=a[n-i+1][m-j+1]);
c[j][0]+=hi+hk;
if(k[i]==1&&k[n-i+1]==1)
{
tt=a[i][j]+a[i][m-j+1]+a[n-i+1][j]+a[n-i+1][m-j+1];
tt=min(4-tt,tt);
f1+=tt;
f2+=tt;
c[j][2]+=tt;
}
else
{
f1+=min(1,hi+hk+(a[i][j]!=a[n-i+1][j]));
f2+=min(1,hi+hk+(a[i][m-j+1]!=a[n-i+1][m-j+1]));
if(k[i]==1||k[n-i+1]==1)
{
tt=a[i][j]+a[i][m-j+1]+a[n-i+1][j]+a[n-i+1][m-j+1];
tt=min(4-tt,tt);
c[j][2]+=tt;
}
else
c[j][2]+=(a[i][j]!=a[n-i+1][j])+(a[i][m-j+1]!=a[n-i+1][m-j+1]);
}
}
c[j][1]=min(f1,f2);
if(n%2==1)
{
c[j][0]+=(k[n/2+1]==1&&a[n/2+1][j]!=a[n/2+1][m-j+1]);
c[j][1]+=(k[n/2+1]==1&&a[n/2+1][j]!=a[n/2+1][m-j+1]);
c[j][2]+=(k[n/2+1]==1&&a[n/2+1][j]!=a[n/2+1][m-j+1]);
}
}
if(m%2==1)
{
for(int i=1;i<=n/2;i++)
{
c[m/2+1][1]+=(a[i][m/2+1]!=a[n-i+1][m/2+1]);
}
}
bbdp();
return;
}
k[x]++;
cnt++;
dfs(x+1);
cnt--;
k[x]--;
dfs(x+1);
return;
}
int main()
{
freopen("dawn.in","r",stdin);
freopen("dawn.out","w",stdout);
cin>>n>>m;
memset(ans,0x3f,sizeof dp);
char cc;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>cc;
a[i][j]=cc-'0';
}
}
if(n>m)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
b[j][i]=a[i][j];
}
}
swap(n,m);
memset(a,0,sizeof a);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j]=b[i][j];
}
}
dfs(1);
for(int i=0;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cout<<ans[j][i]<<' ';
}
cout<<endl;
}
return 0;
}
dfs(1);
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
cout<<ans[i][j]<<' ';
}
cout<<endl;
}
return 0;
}