题目描述给定一个M×NM \times NM×N的二进制矩阵每个元素为000或111矩阵在水平和垂直方向均循环即第111行与第MMM行相邻第111列与第NNN列相邻。两个格子相邻当且仅当它们在同一行且列相邻或同一列且行相邻包括环绕。允许的操作是交换任意两个相邻格子的值相当于将一个111沿相邻方向移动一格。目标是按照以下优先级完成变换同时满足每行拥有相同数量的111且每列也拥有相同数量的111此时输出both以及所需的最少交换次数。若 1 不可能则尝试仅满足每行拥有相同数量的111输出row以及最少交换次数。若 2 也不可能则尝试仅满足每列拥有相同数量的111输出column以及最少交换次数。若以上均不可能输出impossible。输入格式输入第一行为整数TTTT≤10T \le 10T≤10表示测试用例数。每个测试用例第一行包含两个整数M,NM, NM,N2≤M,N≤10002 \le M, N \le 10002≤M,N≤1000分别表示行数和列数。接下来MMM行每行一个长度为NNN的字符串由字符0和1组成表示矩阵的一行。输出格式对于每个测试用例输出一行格式为Case #: solution_type min_swap其中#为用例编号从111开始solution_type为both、row、column或impossible若为后者则无需输出min_swap。若可行min_swap为达到目标所需的最少交换次数可以为000。样例输入2 2 3 001 111 3 3 001 011 000输出Case 1: row 1 Case 2: both 2题目分析本题的核心是在环形网格上通过相邻交换使得行和列的111的个数分别均匀并求出最小交换次数。一次相邻交换等价于将一个111从某个格子移动到与其相邻的格子。由于交换不改变111的总数均匀性只有在总数能被行数或列数整除时才可能实现。因此首先必须判断可行性。若111的总数为total\textit{total}total则若total mod M0\textit{total} \bmod M 0totalmodM0则可以使得每行111的数量相同每行totalM\frac{\textit{total}}{M}Mtotal​个。若total mod N0\textit{total} \bmod N 0totalmodN0则可以使得每列111的数量相同每列totalN\frac{\textit{total}}{N}Ntotal​个。三种情况的优先级已经给出。当两者同时可行时优先输出both。接下来需要计算最小交换次数。由于交换操作是在二维网格上进行的但行方向的移动上下与列方向的移动左右是独立的并且任意一次交换只会改变111的行坐标或列坐标不会同时改变两者因此总交换次数可以分解为垂直方向移动的总步数加上水平方向移动的总步数。对于row情况我们只需要垂直方向移动水平方向不动对于column情况只需要水平方向移动对于both情况两者都需要且总代价为两者之和这是可达到的下界。现在问题转化为一维环形数组上的搬运问题给定一个长度为LLL的环每个位置有一个数值表示当前该行/列的111的数量目标是将每个位置的数值调整为同一个目标值target\textit{target}target每次操作可以将一个单位从某个位置移动到相邻位置环上求最小总移动步数。解题思路一维环上的最优搬运设环上的数组为a[0],a[1],…,a[L−1]a[0], a[1], \ldots, a[L-1]a[0],a[1],…,a[L−1]目标为target\textit{target}target。定义差值d[i]a[i]−targetd[i] a[i] - \textit{target}d[i]a[i]−target显然∑d[i]0\sum d[i] 0∑d[i]0。为了方便考虑将环断开为一条链。若从位置000到L−1L-1L−1顺序计算前缀和P[0]0,P[k]∑i0k−1d[i](1≤k≤L) P[0] 0,\quad P[k] \sum_{i0}^{k-1} d[i] \quad (1 \le k \le L)P[0]0,P[k]i0∑k−1​d[i](1≤k≤L)注意到P[L]0P[L] 0P[L]0与P[0]P[0]P[0]相同因此实际上有LLL个不同的前缀和P[0]∼P[L−1]P[0] \sim P[L-1]P[0]∼P[L−1]。在一条链上非环将盈余搬运到亏空所需的最小代价为∑i0L−1∣P[i]∣\sum_{i0}^{L-1} |P[i]|∑i0L−1​∣P[i]∣。但在环上我们可以选择一个位置 “切开”使得总的搬运距离最小。若选择在位置ccc处切开即认为ccc是链的起点则新的前缀和变为P′[i]P[(ci) mod L]−P[c]P[i] P[(ci) \bmod L] - P[c]P′[i]P[(ci)modL]−P[c]模意义下此时代价为∑i0L−1∣P′[i]∣∑i0L−1∣P[i]−P[c]∣ \sum_{i0}^{L-1} |P[i]| \sum_{i0}^{L-1} |P[i] - P[c]|i0∑L−1​∣P′[i]∣i0∑L−1​∣P[i]−P[c]∣因此最小代价为min⁡c∑i0L−1∣P[i]−P[c]∣ \min_{c} \sum_{i0}^{L-1} |P[i] - P[c]|cmin​i0∑L−1​∣P[i]−P[c]∣这个最小值在P[c]P[c]P[c]取P[0],…,P[L−1]P[0], \ldots, P[L-1]P[0],…,P[L−1]的中位数时达到。因此我们只需计算这些前缀和排序后取中位数再求绝对差之和。算法流程读取矩阵统计每行111的数量rowSum[i]、每列111的数量colSum[j]以及总数total。判断可行性若total % M 0 total % N 0标记both可行。否则若total % M 0标记row可行。否则若total % N 0标记column可行。否则输出impossible。根据优先级选择第一个可行的目标若both可行计算行均匀代价costRow用rowSum和目标值total / M和列均匀代价costCol用colSum和目标值total / N总代价为costRow costCol。否则若row可行只计算costRow。否则若column可行只计算costCol。输出结果。正确性说明可行性判断基于总数是否能被行数或列数整除这是必要条件同时也充分因为我们可以通过相邻交换任意重排111的位置交换操作相当于在网格图上移动111网格图连通因此任意分布都可以达到。分解垂直和水平移动的独立性一次交换只会改变两个相邻格子的行或列不会同时改变两者因此总交换次数等于垂直方向所需总移动次数加上水平方向所需总移动次数且这两个目标可以分别独立实现先做垂直方向的调整再做水平方向的调整或者反之互不影响。一维环上最小搬运代价的推导正确中位数性质保证了最优性。复杂度分析统计行和列O(MN)O(MN)O(MN)。计算一维代价对长度为LLL的数组构造前缀和排序求和时间复杂度O(Llog⁡L)O(L \log L)O(LlogL)。此处需要分别对行和列计算最坏情况O(Mlog⁡MNlog⁡N)O(M \log M N \log N)O(MlogMNlogN)。总复杂度O(MNMlog⁡MNlog⁡N)O(MN M \log M N \log N)O(MNMlogMNlogN)其中M,N≤1000M, N \le 1000M,N≤1000完全可行。空间复杂度O(MN)O(M N)O(MN)。代码实现// Binary Matrix// UVa ID: 12367// Verdict: Accepted// Submission Date: 2026-07-12// UVa Run Time: 0.010s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;longlongminRingCost(constvectorinta,intL,inttarget){vectorlonglongpref(L);pref[0]0;for(inti1;iL;i)pref[i]pref[i-1](a[i-1]-target);sort(pref.begin(),pref.end());longlongmedianpref[L/2];longlongans0;for(longlongx:pref)ansllabs(x-median);returnans;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;for(inttc1;tcT;tc){intM,N;cinMN;vectorintrowSum(M,0),colSum(N,0);inttotal0;string s;for(inti0;iM;i){cins;for(intj0;jN;j)if(s[j]1){rowSum[i];colSum[j];total;}}boolboth(total%M0total%N0);boolrowOk(total%M0);boolcolOk(total%N0);if(both){intRtotal/M;intCtotal/N;longlongcostRowminRingCost(rowSum,M,R);longlongcostColminRingCost(colSum,N,C);coutCase tc: both (costRowcostCol)\n;}elseif(rowOk){intRtotal/M;coutCase tc: row minRingCost(rowSum,M,R)\n;}elseif(colOk){intCtotal/N;coutCase tc: column minRingCost(colSum,N,C)\n;}else{coutCase tc: impossible\n;}}return0;}总结本题的关键在于将二维矩阵的相邻交换分解为两个独立的一维环上搬运问题并利用前缀和中位数求解环形搬运的最小代价。核心技巧包括可行性判断通过总数与行列数的整除关系确定可达到的目标。分解性垂直和水平移动互不干扰总代价可加。环形搬运公式利用前缀和与中位数求出环上的最小搬运步数避免了枚举断点的二次复杂度。该方法适用于类似的行列独立且操作可拆分的矩阵变换问题具有较好的扩展性。