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 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?