Description

Blinker 最近喜欢上一个奇怪的游戏.

这个游戏在一个 \(n \times m\) 的棋盘上玩, 每个格子有一个数. 每次 Blinker 会选择两个相邻的格子, 并使这两个数都加上 \(1\).

现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数, 如果永远不能变成同一个数则输出 \(-1\).

Input

输入的第一行是一个整数 \(T\), 表示输入数据有 \(T\) 轮游戏组成.

每轮游戏的第一行有两个整数 \(n\) 和 \(m\), 分别代表棋盘的行数和列数.

接下来有 \(n\) 行, 每行 \(m\) 个数.

Output

对于每个游戏输出最少能使游戏结束的次数, 如果永远不能变成同一个数则输出 \(-1\).

Sample Input

2
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2

Sample Output

2
-1

Data Range

对于 30% 的数据, 保证 \(T \leq 10, 1 \leq n, m \leq 8\)

对于 100% 的数据, 保证 \(T \leq 10, 1 \leq n, m \leq 40\), 所有数为正整数且小于 \(10^9\).

Explanation

按照黄学长的思路来捋一遍想法:

首先遇到棋盘问题我们需要先给转化成黑白染色的棋盘 (他是这么想的, 但是我没有想到, 所以根本做不出来), 然后统计黑色的和白色的格子各有多少个、和是多少.

记黑色和白色的格子的数量和权值和分别为 \(cnt_0, cnt_1, sum_0, sum_1\).

设最后所有数都会变成 \(x\), 则:

\[cnt_1 \cdot x – sum_1 = cnt_2 \cdot x – sum_2\]

\[x = \frac{sum_1 - sum_2}{cnt_1 - cnt_2}\]

当 \(cnt_1 \neq cnt_2\) 时, 可以直接解出 \(x\) 然后直接判断可能性就可以了.

当 \(cnt_1 = cnt_2\) 时, 如果 \(sum_1 \neq sum_2\) 这个根本无法解出来; 不然我们会发现当某种情况合适时,\(\forall k \gt x\),\(k\) 都是满足条件的, 所以这时候二分搜索然后每一次用网络流判定就可以了.

关于网络流的问题, 详见代码, 建图方法和其他最小割问题相似.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxN = 45, maxn = 2010, maxm = 10010;
const lli infinit = 0x007f7f7f7f7f7f7fll;
#define BLACK 0
#define WHITE 1

class Dinic
{
public:
    struct edge {
        int u, v;
        lli flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    void add_edge(int u, int v, lli flow)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u; q->flow = 0;
        q->next = edges[v]; edges[v] = q;
        p->rev = q; q->rev = p;
        return ;
    }
    int level[maxn];
    bool make_level(void)
    {
        memset(level, 0, sizeof(level));
        queue<int> que;
        que.push(s);
        level[s] = 1;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && !level[ep->v]) {
                    level[ep->v] = level[p] + 1;
                    que.push(ep->v);
                }
        }
        if (level[t] <= 0)
            return false;
        return true;
    }
    lli dfs(int p, lli mn)
    {
        if (p == t)
            return mn;
        lli sum = 0, tmp;
        for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                tmp = dfs(ep->v, min(ep->flow, mn - sum));
                if (tmp > 0) {
                    sum += tmp;
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                }
            }
        if (sum < mn)
            level[p] = 0;
        return sum;
    }
    lli dinic(void)
    {
        lli sum = 0, tmp;
        while (make_level()) {
            tmp = dfs(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
    void clear(void)
    {
        n = s = t = 0;
        ecnt = 0;
        memset(edges, 0, sizeof(edges));
        memset(epool, 0, sizeof(epool));
        memset(level, 0, sizeof(level));
        return ;
    }
} graph;

int T, n, m;
int arr[maxN][maxN],
    color[maxN][maxN];

const int movx[4] = { 0, 0, 1, -1 },
          movy[4] = { 1, -1, 0, 0 };
bool judge(lli target)
{
    lli sum = 0;
    graph.clear();
    graph.n = n*m + 2;
    graph.s = graph.n - 1;
    graph.t = graph.n;
    #define pos(__x,__y) (((__x)-1)*m+(__y))
    rep(i, 1, n) rep(j, 1, m) {
        if (color[i][j]) {
            graph.add_edge(graph.s, pos(i, j), target - arr[i][j]);
            sum += target - arr[i][j];
            rep(k, 0, 3) {
                int nx = i + movx[k], ny = j + movy[k];
                if (nx < 1 || nx > n || ny < 1 || ny > m)
                    continue;
                graph.add_edge(pos(i, j), pos(nx, ny), infinit);
            }
        } else {
            graph.add_edge(pos(i, j), graph.t, target - arr[i][j]);
        }
    }
    if (graph.dinic() >= sum)
        return true;
    return false;
}

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        scanf("%d%d", &n, &m);
        int vmx = 0;
        rep(i, 1, n) rep(j, 1, m) {
            scanf("%d", &arr[i][j]);
            color[i][j] = (i+j) & 1;
            vmx = max(vmx, arr[i][j]);
        }
        // Stating all colours' sum and cnt
        int cnt[2] = { 0, 0 };
        lli sum[2] = { 0, 0 };
        rep(i, 1, n) rep(j, 1, m) {
            sum[color[i][j]] += arr[i][j];
            cnt[color[i][j]] += 1;
        }
        // Multiple cases.
        if (cnt[0] != cnt[1]) {
            lli res = (sum[0] - sum[1]) / (cnt[0] - cnt[1]);
            if (res >= vmx && judge(res))
                printf("%lld\n", res * cnt[1] - sum[1]);
            else
                printf("-1\n");
        } else if (cnt[0] == cnt[1]) {
            if (sum[0] != sum[1]) {
                printf("-1\n");
            } else if (sum[0] == sum[1]) {
                lli l = vmx, r = infinit;
                while (l <= r) {
                    lli mid = (l + r) / 2;
                    if (judge(mid))
                        r = mid - 1;
                    else
                        l = mid + 1;
                }
                printf("%lld\n", l * cnt[1] - sum[1]);
            }
        }
        continue;
    }
    return 0;
}