For fixed final positions of pieces, let us check whether they are possible.

This problem is equivalent to the bipartite matching problem. Specifically, consider a bipartite graph with left vertices corresponding to the initial positions of the pieces, and with right vertices corresponding to the final positions of the pieces, and with edges corresponding to reachable pairs. It suffices to check whether this graph has a complete matching.

It is obvious that existence of a perfect matching is necessary. Sufficiency is shown as follows. First, pick an arbitrary perfect matching. Let us move pieces along with this perfect matching. There can be problems if some pieces collide. This can be circumvented by the following steps:

• If a collision is about to happen, move the piece that originally occupied the cell.
• If the piece that originally occupied the cell cannot move, swap the destination of the two about-to-collide pieces. If that incurs another collision, do the same recursively.

Finally we get a sequence of moves where no pieces collide, which means sufficiency is shown.

Let us maximize the number of operations performed. It is equivalent to maximizing the sum of row numbers and column numbers of final positions. Therefore, it can be solved by converting the aforementioned maximum matching problem to the minimum-cost flow problem.

Let \(K\) be the number of pieces. In a naive graph construction, we would obtain a graph with \(O(K+NM)\) vertices and \(O(KNM)\) edges. We could solve the problem with this construction, but we can do better. If we exploit the fact that the original graph is a grid graph, this problem can be reduced to the minimum cost flow problem on a graph with \(O(NM)\) vertices and \(O(NM)\) edges. Therefore the problem can be solved in \(O(KNM\log(NM))\) time.