题目链接
题意
给你一个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;
}
}