Hello.

Recently I was solving this problem : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2103

Simply the problem says given 12 * n grid of zeros and ones, find the minimum number of swaps to map it to another 12 * n grid where allowed moves are down, up, left and right.

Upon tracing some samples the solution appeared to be minimum cost bipartite matching between non matched ( should be 0 but is 1 or vice versa) one nodes and zero nodes. ( If they are not equal this is impossible). I couldn’t prove correctness so I ran it against a backtracking solution for many small cases, and all passed. Submitted a flow solution and got AC.

Can any body help with proving correctness?