天下一プログラマーコンテスト2015予選A C問題 天下一美術館

天下一プログラマーコンテスト予選A、難しすぎて意味がわからなかった。
ただ、この問題は気づけば一瞬で解けるので、発想が出なかったのが悔しい。

高さH, 横Wの白と黒で表された絵、A,Bがあり、Aの一個の白or黒を反転させる、または隣り合った白と黒を交換、することによって最短で何回でAからBに変えることができるか、という問題。

AとBで異なるところだけ反転させればAからBに変えることができるが、それではコストがA,Bで異なるところ分だけ存在する。しかし、隣り合ったマスを交換することで2つのマスの変更をコスト1で行うことができる。よって隣り合ったマスの交換が最大で何回できるかをカウントする。で、うまく重ならないように隣り合ったマスの組を作っていくわけだが、すごい二部マッチング感が漂う。これに気づけばあとはマスを頂点として二部マッチングしたら終了だ。

この発想欲しかったなぁ…。

MaxFlow<5000> MF(true);

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int H, W; cin >> H >> W;
    int A[H][W], B[H][W];
    rep(i, H) rep(j, W) cin >> A[i][j];
    rep(i, H) rep(j, W) cin >> B[i][j];
    int cnt = 0;
    bool used0[H*W];
    bool used1[H*W];
    memset(used0, false, sizeof(used0));
    memset(used1, false, sizeof(used1));
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            if(A[i][j] != B[i][j]) cnt++;
            if(i+1 < H){
                if(A[i][j] != B[i][j] && A[i+1][j] != B[i+1][j] && A[i][j] != A[i+1][j]){
                    if(A[i][j] == 0){
                        MF.add_edge(i*W+j, (i+1)*W+j, 1);
                        used0[i*W+j] = true;
                        used1[(i+1)*W+j] = true;
                    }else{
                        MF.add_edge((i+1)*W+j, i*W+j, 1);
                        used1[i*W+j] = true;
                        used0[(i+1)*W+j] = true;
                    }
                }
            }
            if(j+1 < W){
                if(A[i][j] != B[i][j] && A[i][j+1] != B[i][j+1] && A[i][j] != A[i][j+1]){
                    if(A[i][j] == 0){
                        MF.add_edge(i*W+j, i*W+j+1, 1);
                        used0[i*W+j] = true;
                        used1[i*W+j+1] = true;
                    }else{
                        MF.add_edge(i*W+j+1, i*W+j, 1);
                        used1[i*W+j] = true;
                        used0[i*W+j+1] = true;
                    }
                }
            }
        }
    }
    for(int i=0; i<H*W; i++){
        if(used0[i]){
            MF.add_edge(H*W, i, 1);
        }
        if(used1[i]){
            MF.add_edge(i, H*W+1, 1);
        }
    }
    cout << cnt - MF.max_flow(H*W, H*W+1) << endl;
}