题意
给定一个 \(n\) 行 \(m\) 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。
现在你可以矩阵实施以下操作：
使用一块钱，选定一个包含 \((1,1)\) 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。
使用三块钱，选定一个包含 \((n,1)\) 的子矩阵，把矩阵中的元素全部反转。
使用四块钱，选定一个包含 \((1,m)\) 的子矩阵，把矩阵中的元素全部反转。
使用两块钱，选定一个包含 \((n,m)\) 的子矩阵，把矩阵中的元素全部反转。
现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。
\(1\le n,m\le 500\)。
题解
首先 \(2,3\) 操作是无用的，只需考虑 \(1,4\) 操作。
整个矩阵取反很难搞，做个简单的变形：\(s_{i,j}=a_{i,j}\oplus a_{i,j+1}\oplus a_{i+1,j}\oplus a_{i+1,j+1}\)，则操作 \(1\) 是单点取反，操作 \(4\) 是同时取反 \((x,y),(x,m),(n,y),(n,m)\)。倒着考虑，目标态是全为 \(0\)。称操作 \(4\) 为 \(\operatorname{op}(x,y)\)。
接下来是两个重要结论：
- \(\operatorname{op}(x,y)\) 的必要条件是 \(s_{x,y}=s_{x,m}=s_{n,y}=1\)。因为如果不是，操作后至少还需要 \(1\) 的代价使这三位都归零。不如直接三次操作 \(1\)。
- 不存在 \(\operatorname{op}(x_1,y_1),\operatorname{op}(x_2,y_2)\)，有 \(x_1=x_2\) 或 \(y_1=y_2\)。因为如果存在，不妨设为 \(y_1=y_2\)，则 \((n,y_1),(n,m)\) 两位是不动的，另外 \(4\) 位直接操作 \(1\) 即可。
第二个结论提供了很好的二分图模型。再稍加推导，易知答案为 \(rem-k\)，其中 \(rem\) 为 矩阵变换后 \(1\) 的数目，\(k\) 为最大匹配。\((n,m)\) 处需特殊判断。