如果(2 otmid M)，就把两个图折一下，把(N M)互换，这样就可以保证(2 mid M)。
因为操作可逆，所以我们可以选择一个中间状态，把起始和终点状态都变成这个状态，我们就可以得到一组方案。我们可以选择最特殊的：所有方块都是横着放的状态。那么我们现在只需要知道这两个状态转移到它的方案。
我们从上往下、从左往右考虑，如果遇到了一个竖着的方块就把它调成横着的：如果这个方块的右边是一个竖着的块或者两个横着的块就直接交换，如果是一个横着的一个竖着的，我们需要把下面的竖着的变成横着的，这就是一个子问题，递归解决即可。
不难得到操作数为(N^3)级别。