757. 修改矩阵

我们称一个矩阵为黑白矩阵，当且仅当对于该矩阵中每一个位置如(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≤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

解析：

先来分析下题意：
题中定义的黑白矩阵意思是

image.png

首先 对于（1,1）点，我们发现上下左右四个元素均需相等

然后我们再来看其他店 例如我们来看（1,1）点和（3,1）两个红色元素点
会发现两个点中间的相邻元素有公用的值
而对于任意两个蓝色元素，也有也是一样
那么我们可以吧这个矩阵分为奇数格子和偶数格子
如果要成为一个黑白矩阵，就要所有的奇数格子的值相同，所有偶数格子的值相同，并且奇数格子的值不等于偶数格子。

题目要我们求出把一个矩阵改变为黑白矩阵所需要改变的最少格子数量，
也就是说找到奇数格子和偶数格子中分别出现的最多的数字 a1 b1 如果a1≠b1 那么久直接按照这个填充 如果相等的话 我们再看第二多的 a2 b2
然后从 a1 a2 b1 b2 的排列中 找到最大的数量res

最后用n*m-res 便为结果

#include<iostream>
#include <unordered_map>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int,int> PII;

int main()
{
    unordered_map<int,int>oddNum,evenNum;
    
    int n,m;
    cin>>n>>m;
    
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int temp;
            cin>>temp;
    
            if((i+j)%2)
            {
                oddNum[temp]++;
            }
            else
            {
                evenNum[temp]++;
            }
        }
    }
    

    vector<PII> a,b;
    
    for(auto item:oddNum)
    {
        a.push_back({item.second,item.first});
    }
    for(auto item2:evenNum)
    {
        b.push_back({item2.second,item2.first});
    }
    
    sort(a.begin(),a.end()),reverse(a.begin(),a.end());
    sort(b.begin(),b.end()),reverse(b.begin(),b.end());
    
    int res=0;
    
    for(int i=0;i<2&&i<a.size();i++)
        for(int j=0;j<2&&b.size();j++)
        {
            if(a[i].second==b[j].second)
                res=max(res,max(a[i].first,b[j].first));
            else
                res=max(res,a[i].first+b[j].first);
        }
    
    
    cout<<n*m-res;
    
    return 0;
    
}