题意

给你一个n*m的01矩阵，现在我们要从起点(1,1)到(n,m)并且每一步只能向下或者向右走，现在要求他能走到终点的路径必须全部是回文(比如01010)，问最少改动多少个元素，使得条件满足$(2≤n,m≤30)$

Input

4
2 2
1 1
0 1
2 3
1 1 0
1 0 0
3 7
1 0 1 1 1 1 1
0 0 0 0 0 0 0
1 1 1 1 1 0 1
3 5
1 0 1 0 0
1 1 1 1 0
0 0 1 0 0

Output

0
3
4
4

题解

• 点(i,j)是由(1,1)走i+j−2步到达的，比如(1,1)走1步能到(1,2)和(2,1)

• 所以把走k步到达的点记作一个集合,记录每个集合1的数目和0的数目

• 走k步到的点集要和走n+m−2−k到的点集相等(回文)

• 要么同时为1,要么同时为0,所以选1的个数和0的个数当中较小的数目进行修改，累加所有集合代价即可

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<double,int> pdi;
typedef long long LL;
const int INF=0x3f3f3f3f;

const int N=35;
int cnt[N<<1][2];
int g[N][N];
int n,m;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(cnt,0,sizeof cnt);
        cin>>n>>m;

        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>g[i][j];

        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cnt[i+j-2][g[i][j]]++;

        int len=n+m-2;
        int ans=0;
        for(int i=0,j=len;i<j;i++,j--)
            ans+=min(cnt[i][0]+cnt[j][0],cnt[i][1]+cnt[j][1]);

        cout<<ans<<endl;
    }

   // system("pause");
}