问题分析 题目要求我们根据给定的 $(n-1)\times(m-1)$ 矩阵 $b$ 还原出原始的 $n\times m$ 矩阵 $a$，其中 $b_{i,j} = a_{i,j} + a_{i,j+1} + a_{i+1,j} + a_{i+1,j+1}$。

关键思路 变量关系建立：

通过观察 $b$ 矩阵的定义，可以发现相邻的 $a$ 元素之间存在线性关系

将 $a$ 矩阵的元素看作变量，$b$ 矩阵的元素提供了这些变量之间的约束条件

差分约束系统：

将问题转化为差分约束系统，其中每个 $a_{i,j}$ 需要满足 $0 \leq a_{i,j} \leq 10^6$

通过巧妙的变量替换，将原问题转化为关于行变量和列变量的约束系统

图模型构建：

将行和列分别作为图中的节点，建立二分图模型

根据 $(i+j)$ 的奇偶性确定边的方向，构建带权有向图

负环检测：

使用 SPFA 算法检测图中是否存在负环

如果存在负环，说明约束系统无解，输出 "NO"

如果不存在负环，可以根据最短路径值构造出满足条件的解

算法流程 初始化：将第一行和第一列设为 0，作为参考基准

推导关系：根据 $b$ 矩阵递推计算其他 $a$ 元素的关系表达式

建图：根据奇偶性建立行与列之间的约束边

最短路：使用 SPFA 检测负环并计算最短路径

构造解：根据最短路径值调整初始矩阵，得到最终解

复杂度分析 时间复杂度：$O(T \cdot (n \cdot m + (n+m)^3))$，主要取决于 SPFA 算法

空间复杂度：$O(n \cdot m + n + m)$

算法特点 该方法巧妙地将矩阵还原问题转化为图论中的差分约束问题，通过检测负环来判断解的存在性，并利用最短路径值构造出满足所有约束的可行解。这种转换使得原本复杂的问题可以通过标准的图算法高效解决。