Educational Codeforces Round 89 (Rated for Div. 2) C - Palindromic Paths(回文路径,思维)

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

思路:
例:矩阵为
Educational Codeforces Round 89 (Rated for Div. 2) C - Palindromic Paths(回文路径,思维)
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;
    }
}
上一篇:CF695 D. Sum of Paths(DP)


下一篇:【Codeforces Round #695 (Div. 2) D】Sum of Paths