题意简述

给定 $n\times m$ 矩阵，每次操作可将一行全部替换为当前各列的异或和，或将一列全部替换为当前各行的异或和。操作任意次后，求所有相邻格子之差的绝对值之和的最小值。

性质分析

记 $f(i)$ 为第 $i$ 行的异或和，$g(j)$ 为第 $j$ 列的异或和。

性质1：无论怎样操作，整个矩阵的异或和（所有元素异或）保持不变。
性质2：对行操作时，是将该行所有元素设为 $g(j)$；对列操作同理。
性质3：经过任意次操作后，矩阵必然满足一个“线性”条件：每一行的元素要么是原列异或和，要么是原行异或和，且所有行的元素由列异或和决定。可以证明，最终矩阵的形态等价于我们选定一个“删除”的行 $r$ 和列 $c$，然后在剩下的 $(n-1)\times (m-1)$ 子矩阵中自由排列行向量和列向量，而最终矩阵的元素由删除的行列和排列决定。具体来说，将原矩阵扩展一行一列：增加第 $n$ 行（最下方）存储每一列的异或和，增加第 $m$ 列（最右侧）存储每一行的异或和，右下角为全矩阵异或和。操作后矩阵相当于从中删去某一行 $i$ 和某一列 $j$，然后用剩余的行/列异或和填充，使得剩余部分形成一个合法的矩阵。

关键结论：我们可以选择最终矩阵的“基准行”和“基准列”（即删去的行列），然后其他行和列在异或约束下，通过调整顺序使相邻差之和最小。最终答案等于：枚举删去的行 $i$ 和列 $j$，对剩余的行和列分别求一个排列顺序，使得相邻行之间的元素差绝对值之和最小，加上相邻列之间的同样代价。两部分的代价独立可加。

算法设计

1. 扩展矩阵：读入 $n\times m$ 后，计算 $a[i][m]$（第 $i$ 行异或和），$a[n][j]$（第 $j$ 列异或和），$a[n][m]$（全异或和）。现在矩阵大小为 $(n+1)\times (m+1)$。
2. 枚举删除的行 $rmv$（0..n）和列 $rmv$（0..m）。
   • 对于固定的 $rmv$ 列，我们需要安排其余 $n$ 行的顺序（因为我们固定了一行被删除，但注意代码中实际是枚举 $rmv$ 行和 $rmv$ 列，然后处理剩下的行和列）。令 $fullmask_n = (1<<(n+1))-1$，总行数 $n+1$。在对列进行删除时，我们考虑除删除列外的其他 $m$ 列的顺序。
3. 行排列代价：对于固定的删除列 $rmv$，计算任意两行 $i,j$ 之间的“贡献” $w[i][j]$：为 $\sum_{l \neq rmv} |a[i][l] - a[j][l]|$。然后使用状压 DP 求一条哈密顿路径，使得经过所有行（共 $n$ 行，注意行的总数是 $n$ 还是 $n+1$？代码中 if (__builtin_popcount(mask) == n) continue; 表示我们只走 $n$ 步，因为总共有 $n+1$ 行，但我们排除了删除行，要走遍剩下的 $n$ 行）。DP 状态 dp[last][mask] 表示当前在行 last，已经过的行集合为 mask 的最小代价。最后对于每个可能的结尾行 $i$，记录 fr[i][rmv] 为不包含行 $i$ 的集合（全集中去掉 $i$）对应的最小路径代价，这实际上对应了以行 $i$ 为“删除行”时，其余行排列的最小代价。
   • 仔细看：$fr[i][rmv]$ 定义为：删除列 $rmv$，并且最终删去的行是 $i$ 时，剩余 $n$ 行的最小相邻代价。DP 完成后，$ fr[i][rmv] = min_{last} dp[last][fullmask_n ^ (1<<i)] $。
4. 列排列代价：对称地，枚举删除的行 $rmv$，计算任意两列 $i,j$ 的 $w[i][j]$（忽略删除行），对列进行状压 DP，得到 $fc[rmv][j]$：删除行 $rmv$ 且最终删除列为 $j$ 时，剩余 $m$ 列的最小相邻代价。
5. 答案：$ans = \min_{i,j} (fr[i][j] + fc[i][j])$。即枚举最终删除的行 $i$ 和列 $j$，两部分代价相加取最小。

时间复杂度：枚举 $rmv$ 列 $O(m)$，行状压 DP $O(n^2 2^n)$；同理列状压 $O(m^2 2^m)$。由于 $n,m\le 15$，加上枚举，总运算量在可接受范围内（$\sum n^2 2^n \le 500\times 2^{15}\approx 1.6\times 10^7$）。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 16;

int n, m;
int a[N][N];

int fr[N][N], fc[N][N];
int w[N][N], dp[N][1<<N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int t;
    cin >> t;

    while (t--) {
        cin >> n >> m;

        for (int i = 0; i <= n; i++) a[i][m] = 0;
        for (int j = 0; j <= m; j++) a[n][j] = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> a[i][j];
                a[i][m] ^= a[i][j];
                a[n][j] ^= a[i][j];
                a[n][m] ^= a[i][j];
            }
        }

        int fullmask_n = (1 << (n+1)) - 1;
        int fullmask_m = (1 << (m+1)) - 1;

        for (int rmv = 0; rmv <= m; rmv++) {
            for (int i = 0; i <= n; i++) {
                for (int j = i + 1; j <= n; j++) {
                    w[i][j] = 0;
                    for (int l = 0; l <= m; l++) {
                        if (rmv == l) continue;
                        w[i][j] += abs(a[i][l] - a[j][l]);
                    }
                    w[j][i] = w[i][j];
                }
            }

            for (int i = 0; i <= n; i++) {
                fill(dp[i], dp[i] + fullmask_n, INT_MAX);
                dp[i][1 << i] = 0;
            }

            for (int mask = 0; mask <= fullmask_n; mask++) {
                for (int last = 0; last <= n; last++) {
                    if (~mask >> last & 1) continue;
                    if (__builtin_popcount(mask) == n) continue;

                    for (int next = 0; next <= n; next++) {
                        if (mask >> next & 1) continue;

                        int new_mask = mask | 1 << next;
                        dp[next][new_mask] = min(
                            dp[next][new_mask],
                            dp[last][mask] + w[last][next]
                        );
                    }
                }
            }

            for (int i = 0; i <= n; i++) {
                fr[i][rmv] = INT_MAX;
                int mask = fullmask_n ^ 1 << i;

                for (int last = 0; last <= n; last++) {
                    fr[i][rmv] = min(fr[i][rmv], dp[last][mask]);
                }
            }
        }

        for (int rmv = 0; rmv <= n; rmv++) {
            for (int i = 0; i <= m; i++) {
                for (int j = i + 1; j <= m; j++) {
                    w[i][j] = 0;
                    for (int l = 0; l <= n; l++) {
                        if (rmv == l) continue;
                        w[i][j] += abs(a[l][i] - a[l][j]);
                    }
                    w[j][i] = w[i][j];
                }
            }

            for (int i = 0; i <= m; i++) {
                fill(dp[i], dp[i] + fullmask_m, INT_MAX);
                dp[i][1 << i] = 0;
            }

            for (int mask = 0; mask <= fullmask_m; mask++) {
                for (int last = 0; last <= m; last++) {
                    if (~mask >> last & 1) continue;
                    if (__builtin_popcount(mask) == m) continue;

                    for (int next = 0; next <= m; next++) {
                        if (mask >> next & 1) continue;

                        int new_mask = mask | 1 << next;
                        dp[next][new_mask] = min(
                            dp[next][new_mask],
                            dp[last][mask] + w[last][next]
                        );
                    }
                }
            }

            for (int i = 0; i <= m; i++) {
                fc[rmv][i] = INT_MAX;
                int mask = fullmask_m ^ 1 << i;

                for (int last = 0; last <= m; last++) {
                    fc[rmv][i] = min(fc[rmv][i], dp[last][mask]);
                }
            }
        }

        int ans = INT_MAX;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                ans = min(ans, fr[i][j] + fc[i][j]);
            }
        }

        cout << ans << '\n';
    }
}