EducationalCodeforcesRound89(RatedforDiv.2)C-PalindromicPaths(回文路径，思维)无愧于人-

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

思路:
例:矩阵为

1.首先，要是路径为回文，那么我现在走的第一步，和最后走的一步肯定要相等(废话)。

2.首先从起点我们第一步能走到(1,2)和(2,1)这俩个坐标，那么他们走到的最后一步是(n-1,m)和(n,m-1)，根据要求那么(1,2)必须要和(n-1,m)和(n,m-1)相等，也就是这三个点必须相同，同理:(2,1)也必须和(n-1,m)和(n,m-1)相同。那么得出(1,2)和(2,1)也要相等。
那么综上可得，从起点走的第一步能到达的所有点，必须和从起点走的最后一步相等(或者说从终点走向起点的第一步)，也就是一个对称结构。

3.那么我们枚举每一步，把每一步的最少改动数目求出来即可。

假如我们现在需要8步。
第0步:也就是在起点的这一步,1.
第1步:0 0 表示可以走到的元素
第2步:1 0 1
第3步:1 0 1
第4步…
第5步…
第6步…
第7步…
第8步…
那么第0步对第8步
第1步对第7步
2对6 3对5 第4步就可以不改动

这里说得有点啰嗦了，但是我怕你们看不懂代码。。。。。

AC代码

#include <bits/stdc++.h> inline long long read(){char c = getchar();long long x = 0,s = 1; while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();} while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();} return x*s;} using namespace std; #define NewNode (TreeNode *)malloc(sizeof(TreeNode)) #define Mem(a,b) memset(a,b,sizeof(a)) #define lowbit(x) (x)&(-x) const int N = 1e5 + 10; const long long INFINF = 0x7f7f7f7f7f7f7f; const int INF = 0x3f3f3f3f; const double EPS = 1e-7; const unsigned long long mod = 998244353; const double II = acos(-1); const double PP = (II*1.0)/(180.00); typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> piil; int main() {     std::ios::sync_with_stdio(false);     cin.tie(0),cout.tie(0); int t;     cin >> t; while(t--) { int n,m;         cin >> n >> m; int arr[n+5][m+5] = {0};         vector<int> v[100];//存储每一步 for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) {                 cin >> arr[i][j]; int num = (i-1)+(j-1),num1 = (n-i)+(m-j);//求第几步 //num表示从起点起是第几步，num1表示从终点起是第几步 //把对称的一步记录下来                 v[min(num,num1)].push_back(arr[i][j]); } } int num = (m-1)+(n-1),sum = 0,k;//num为总步数         num % 2 == 0 ? k = num/2-1 : k = num/2;//求出必须要改变的k步，上面解释过了，如果步数为偶数，有一步是不用变的 for(int i = 0;i <= k;i++)//枚举每一步 { int num0 = 0,num1 = 0; for(int j = 0;j < v[i].size();j++)                 v[i][j] == 0 ? num0++ : num1++;             sum += min(num0,num1);//算出必须要改变的最小值 }         cout << sum << endl; } }