解题思路
路径上每个格子把 X 与 Y 分入两个账户,对差值的贡献恰为 ±(X−Y)。因此 ∣S−T∣ 等于某条从 (1,1) 到 (N,M)(只向右或向下)的路径上,各格 ±(Xi,j−Yi,j) 之和的绝对值的最小值。
N,M≤80,路径长度不超过 N+M−1,每个 ∣X−Y∣≤80,可达差的绝对值不超过 80(N+M−1)。用 bitset 记录到达每个格子时所有可能的带偏移差分:令偏移 sh=80(N+M),从上方或左方转移时把集合整体左右平移 ∣X−Y∣。最后在终点集合中找离 0 最近的值。
复杂度分析
时间复杂度 O(NM⋅w(N+M)V),其中 V=80,w 为字长。空间复杂度 O(NM⋅w(N+M)V)。