题解

思路

把初始矩阵中多出的 $1$ 看作供给，把目标矩阵中缺少的 $1$ 看作需求。一次相邻交换会让一个 $1$ 沿网格边移动一步，因此问题等价于在梯形网格上以曼哈顿距离匹配所有供给与需求。

做法

子任务 1：状态图 BFS

把 $2n$ 个格子的 01 状态压成一个二进制整数。每条网格边上若两端不同，就可以交换并到达一个新状态。对状态图 BFS 可直接得到最短交换次数。

子任务 2：最小费用完美匹配

列出初始矩阵和目标矩阵中所有 $1$ 的位置。若数量不同则无解；否则建立完全二分图，边权为两位置的曼哈顿距离。使用匈牙利算法求最小费用完美匹配。

任意交换序列都定义了初始 $1$ 到目标 $1$ 的匹配，代价不小于对应距离和。反过来，网格上的单位运输可以沿最短路实现，所以最小匹配费用就是答案。

子任务 3：按列贪心

若某格初始为 $1$、目标为 $0$，称为供给；反之称为需求。已经相同的格子无需移动。

从左到右处理每一列。先把本列两个格子的供给或需求加入各自行队列，然后按如下顺序配对：

1. 同一行的供给与需求尽量配对；
2. 若仍同时存在供给与需求，再跨行配对。

一对位于 $(r_1,c_1),(r_2,c_2)$ 的格子贡献 $|c_1-c_2|+[r_1\ne r_2]$。

处理完每一列后，不可能同时剩余未匹配供给和未匹配需求。所有仍未匹配的点都在已处理前缀中，未来点与它们的水平距离之和不取决于同类点之间的具体对应；因此优先同一行只会最小化额外的纵向费用，不会增加水平费用。交换论证说明该贪心始终存在于某个最优匹配中。

正确性证明

引理 1 最少交换次数等于所有供给与需求之间最小曼哈顿距离匹配的费用。

证明：每次交换至多使某个 $1$ 沿一条边移动一步，故任意方案给出同费用的运输与匹配；任意匹配又可沿最短路逐单位运输实现，所以二者相等。

引理 2 按列算法匹配一对同一行端点不会使最优费用变大。

证明：当前列之前的所有未匹配点都位于左侧，水平费用只由左右端点列坐标之和决定，与具体对应无关。同一行配对的纵向费用为零，是可选配对中的最小值。

引理 3 同行配对完成后，若供给和需求都存在，立即跨行配对是安全的。

证明：此时二者必在不同行，任何保留到未来的方案也至少需要一次纵向移动；立即配对不会改变所有匹配的水平费用，并支付最小可能的纵向费用一。

定理 按列贪心输出最少交换次数。

证明：由引理 2、3，每一步都能把某个最优匹配改造成包含当前贪心配对且费用不增。归纳后得到贪心匹配为最小费用匹配，再由引理 1 得到结论。数量不同或最后仍有未匹配点时显然无解。

复杂度

子任务 1 时间复杂度为 $O(2^{2n}n)$。子任务 2 时间复杂度为 $O(k^3)$，其中 $k$ 是 $1$ 的数量。满分算法时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。