题目描述

我们称一个矩阵为黑白矩阵，当且仅当对于该矩阵中每一个位置如(i, j)，其上下左右四个方向的数字相等，即(i-1, j)、(i+1, j)、(i, j-1)、(i, j+1)四个位置上的数字两两相等且均不等于(i, j)位置上的数字。（超出边界的格子忽略）

现在给出一个 n*m 的矩阵，我们想通过修改其中的某些数字，使得该矩阵变成黑白矩阵，请问最少需要修改多少个数字。

输入格式
第一行包含两个整数n和m，表示矩阵的长宽。

接下来n行，每行包含m个整数，用来表示整个矩阵。

输出格式
仅包含一个整数，表示原矩阵变为黑白矩阵最少修改的数字数量。

数据范围

1≤n,m≤1051≤n,m≤105,
1≤n∗m≤105

样例

输入样例1：

3 3
1 1 1
1 1 1
1 1 1

输出样例1：

4

输入样例2：

3 3
1 1 1
1 5 1
1 1 1

输出样例2：

4

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int main()
{
    unordered_map<int,int> a,b;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int t;
            cin>>t;
            if(i+j&1)a[t]++;
            else b[t]++;
        }

    vector<PII> aa,bb;
    for(auto x:a)aa.push_back({x.second,x.first});
    for(auto x:b)bb.push_back({x.second,x.first});

    sort(aa.begin(),aa.end());
    reverse(aa.begin(),aa.end());

    sort(bb.begin(),bb.end());
    reverse(bb.begin(),bb.end());

    int ans= -1;
    for(int i=0;i<2&&i<aa.size();i++)
        for(int j=0;j<2&&j<bb.size();j++)
        {
            if(aa[i].second!=bb[j].second)
                ans=max(ans,aa[i].first+bb[j].first);
            else
                ans=max(ans,max(aa[i].first,bb[j].first));
        }
    if(aa.empty())ans=bb[0].first;
    if(bb.empty())ans=aa[0].first;
    cout<<n*m-ans<<endl;
    return 0;
}