助手Christina发明了一种方格取数的新玩法：在n*m的方格棋盘里，每个格子里写一个数。两个人轮流给格子染色，直到所有格子都染了色。在所有格子染色完后，计算双方的分数。对于任意两个相邻（即有公共边）的格子，如果它们都被同一个人染色，那么这个人将得到这两个格子中的数的异或的分数。所有的分数加和计算。

现在，Christina用这个游戏来挑战你，想让你一败涂地，因此她总是采用最优策略使得她的分数尽可能地比你多。为了不输得太惨，你需要知道自己最多比助手多多少分数，或最少比助手少多少分数——也就是你的得分减去助手的得分最大是多少。（先后手由输入给定）

输入

第一行一个正整数T，表示数据组数。

对于每组数据，输入第一行为三个整数n,m,f。其中f为0或1，当f=0,你是先手，当f=1,你是后手。

接着输入n行，每行m个非负整数，表示格子里的数。

输入保证2<=n,m<=400。格子里的数均为不超过int范围的非负整数。

此题有多组数据，数据组数T<=10。

输出

对于每一组数据，输出一行一个整数：你的得分减去助手的得分的最大值。

SOURCE：codeforces

输出时每行末尾的多余空格，不影响答案正确性

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <vector>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

#define debug(a) cout << #a << " " << a << endl

using namespace std;

const int maxn = 4*1e2 + 10;

const int mod = 1e9 + 7;

typedef long long ll;

ll mapn[maxn][maxn], a[maxn*maxn];

ll dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };

bool cmp( ll x, ll y ) {

    return x > y;

}

int main() {

    ll t;

    cin >> t;

    while( t -- ) {

        ll n, m, f;

        memset( a, 0, sizeof(a) );

        cin >> n >> m >> f;

        for( ll i = 0; i < n; i ++ ) {

            for( ll j = 0; j < m; j ++ ) {

                cin >> mapn[i][j];

            }

        }

        ll cnt = 0;

        for( ll i = 0; i < n; i ++ ) {

            for( ll j = 0; j < m; j ++ ) {

                a[cnt] = 0;

                for( ll k = 0; k < 4; k ++ ) {

                    ll x = i + dx[k];

                    ll y = j + dy[k];

                    if( x >= 0 && x < n && y >= 0 && y < m ) {

                        a[cnt] += (mapn[i][j]^mapn[x][y]);

                    }

                }

                cnt ++;

                //cout << a[cnt-1] << " ";

            }

            //cout << endl;

        }

        sort( a, a + cnt, cmp );

        ll sum1 = 0, sum2 = 0;

        for( ll i = 0; i < cnt; i ++ ) {

            if( i&1 ) {

                sum2 += a[i];

            } else {

                sum1 += a[i];

            }

        }

        //因为要取到相邻的所有点的时候才能得到结果，然而在我们实际的运算

        //结果中只取到了这些结果点的一半相邻点，所以要除以二

        if( !f ) {

            cout << ( sum1 - sum2 ) / 2 << endl;

        } else {

            cout << ( sum2 - sum1 ) / 2 << endl;

        }

    }

    return 0;

}