Strong Brickwork

题目大意：给一个N＊M(N, M均为偶数，且不超过100)的棋盘，该棋盘有两层，使用1*2的骨牌覆盖，现在给你第一层的覆盖方案，要你求出符合以下要求的任意一个完全覆盖第二层的方案：

  • 一块骨牌不能完全放在第一层的某块骨牌上
    也就是说第二层的每一块骨牌必须同时在第一层的两块不同的骨牌上面
    看到棋盘还跟骨牌覆盖方案有关，很容易就会想到那个——二分图匹配。构图也很简单，先把格子黑白染色分类，想像一下平时看到的国际象棋棋盘。然后对于每个黑色格子（或白色），如果跟他相邻的格子，如果他们不在同一块骨牌上就连一条边，这样就构图完毕了，跑一边完全匹配，如果刚好有匹配成功(N*M)/2条边就说明有解。 做这道题算是试了一下匈牙利算法的模版，然后写的时候一开始染色分类的时候写错了，纠结了好久=_=。



    input
    output



2 4
1 1 2 2
3 3 4 4



2 1 1 4
2 3 3 4





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;

const int MN = 110;

int n, m, tot;
int mp1[MN][MN] = {0};
int mp2[MN][MN] = {0};
int from[MN*MN] = {0};
vector<int> g[MN*MN];
bool use[MN*MN];

bool match(int x) {
    for (int i = 0; i < g[x].size(); i++)
        if (!use[g[x][i]]) {
            use[g[x][i]] = true;
            if (from[g[x][i]] == -1 || match(from[g[x][i]])) {
                from[g[x][i]] = x;
                return true;
            }
        }
    return false;
}

int hungary() {
    tot = 0;
    memset(from, 255, sizeof(from));
    for (int i = 0; i < n*m; i++) {
        memset(use, 0, sizeof(use));
        if (match(i)) tot++;
    }
    return tot;
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &mp1[i][j]);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) if ((i+j)%2 != 0) {
            if ((j+1 < m) && (mp1[i][j] != mp1[i][j+1]))
                g[i*m+j].push_back(i*m+j+1);
            if ((i+1 < n) && (mp1[i][j] != mp1[i+1][j]))
                g[i*m+j].push_back((i+1)*m+j);
            if ((j-1 >= 0) && (mp1[i][j] != mp1[i][j-1]))
                g[i*m+j].push_back(i*m+j-1);
            if ((i-1 >= 0) && (mp1[i][j] != mp1[i-1][j]))
                g[i*m+j].push_back((i-1)*m+j);
        }
    }

    int ans = 0;
    ans = hungary();
    if (ans == (n*m/2)) {
        memset(mp2, 255, sizeof(mp2));
        int k = 0;
        for (int i = 0; i < n*m; i++)
            if (from[i] != -1) {
                k++;
                mp2[from[i]/m][from[i]%m] = k;
                mp2[i/m][i%m] = k;
            }
        for (int i = 0; i< n; i++) {
            printf("%d", mp2[i][0]);
            for (int j = 1; j < m; j++)
                printf(" %d", mp2[i][j]);
            cout << endl;
        }
    } else {
        cout << -1 << endl;
    }
    return 0;
}