网易70：翻转翻转

给定一个N*M的矩阵，在矩阵中每一块有一张牌，我们假定刚开始的时候所有牌的牌面向上。
现在对于每个块进行如下操作：

翻转某个块中的牌，并且与之相邻的其余八张牌也会被翻转。
XXX
XXX
XXX
如上矩阵所示，翻转中间那块时，这九块中的牌都会被翻转一次。
请输出在对矩阵中每一块进行如上操作以后，牌面向下的块的个数。

方法1：常规贪心法（数据量太大超内存）

#include<iostream>
#include<vector>
using namespace std;
/*
整体思路：贪心算法
对每一块进行翻转，并检查其3*3范围内的牌是否符合翻转要求，若符合，则也进行翻转。
在这里用偶数0表示初始状态，每翻转一次+1，直到最后，检查奇数的个数即为结果
*/
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        //创建n*m的矩阵,初始化为0
        vector<vector<int> > poker(n, vector<int>(m, 0));
        //创建3*3范围内的dx,dy
        vector<int> dx = { -1,-1,-1,0,0,1,1,1 };
        vector<int> dy = { -1,0,1,-1,1,-1,0,1 };
        //对poker矩阵中的每一个点翻转，并判断其3*3邻域内点是否需要翻转
        for (int x = 0; x < n; x++)
        {
            for (int y = 0; y < m; y++)
            {
                //首先自己先翻转
                poker[x][y] += 1;
                //再判断3*3邻域内点是否要翻转,满足限制条件即可
                for (int dxy = 0; dxy < dx.size(); dxy++)
                {
                    int nextx = x + dx[dxy], nexty = y + dy[dxy];
                    if (nextx >= 0 && nextx < n && nexty >= 0 && nexty < m)
                    {
                        poker[nextx][nexty] += 1;
                    }
                }
            }
        }
        int sumOdd = 0;
        for (int x = 0; x < n; x++)
        {
            for (int y = 0; y < m; y++)
            {
                if (poker[x][y] % 2 != 0)
                    sumOdd += 1;
            }
        }
        cout << sumOdd << endl;
        poker.clear();
    }
}

方法2：找规律

#include<iostream>
#include<vector>
using namespace std;
/*
整体思路：找规律
观察一个点在以自己为中心的3*3邻域内有多少个邻居。
若有奇数个邻居，则这奇数个邻居的翻转会影响此点，邻居影响奇数次，而且此点也会自己翻转一次。所以总翻转次数为偶次，保持不动
若有偶数（包括零）个邻居，则它的偶数个邻居翻转会影响此点，邻居影响偶数次，自己会翻转一次，所以总翻转次数为奇数次，变化。
总结：若邻居为奇数，保持不变；若邻居为偶数，变化。
所以此题可以改换成找邻居为偶数个点的个数：
1*1类型的：0
1*n或n*1类型的（n>1）:n-2
n*m类型（n>1且m>1）:(n-1)*(m-1)
*/
int main()
{
    long long t;
    cin>>t;
    while(t--)
    {
        long long n,m;
        cin>>n>>m;
        if(n==1&&m==1)
            cout<<1<<endl;
        else if((n==1&&m>1)||(n>1&&m==1))
            cout<<max(n,m)-2<<endl;
        else
            cout<<(n-2)*(m-2)<<endl;
    }
    return 0;
}