官方题解对本题结论未加详细推导，较为简略，这里希望给出一个较为详细的证明。
以下记位置 $(x, y)$ 的 "标号" 为 $(a_{x, y}, b_{x, y})$ (与题面中记号含义相同)，同时不区分 "位置 $(x, y)$ " 与 "位置 $(x, y)$ 上的数"。
首先，考虑刻画矩阵的合法条件。
通过打表，发现当且仅当含有形如 $\begin{pmatrix} 0 & 1 \\ 1 & ? \end{pmatrix}$ (其中 $?$ 可以任取 $0$ 或 $1$ ) 或 $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ 的子矩阵，原矩阵不合法。
结论一：若含有 $\begin{pmatrix} 0 & 1 \\ 1 & ? \end{pmatrix}$ 子矩阵，则原矩阵不合法。
考虑找到最靠左上的这样的子矩阵，记 $0$ 的位置为 $(x_0, y_0)$，其右方 $1$ 的位置为 $(x_0, y_1)$，下方 $1$ 的位置为 $(x_1, y_0)$。
由于要求最靠左上，必有 $(x_0, y_0+1), (x_0, y_0+2), \cdots, (x_0, y_1-1)$ 均为 $0$。类似的，$(x_0+1, y_0), (x_0+2, y_0), \cdots, (x_1-1, y_0)$ 也均为 $0$。
找到 $(x_0, y_0)$ 上方第一个 $1$，记其位置为 $(x_0', y_0)$。
暂时将 $(x_0, y_0)$ 视为 $1$，记 $(x_0, y_0)$ 的标号为 $(p, q)$，$(x_0', y_0)$ 的标号为 $(p', q')$，考虑分析 $p, p'$ 的大小关系与 $q, q'$ 的大小关系。
对 $q, q'$，由于 $(x_0, y_0)$ 与 $(x_0', y_0)$ 间全是 $0$，不难发现 $q' = q-1$。
对 $p, p'$，考察 $(x_0', y_0)$ 左方的格子 $(x_0', y)\ (y < y_0)$ 与 $(x_0, y_0)$ 左方对应的格子 $(x_0, y)$。
若 $(x_0', y)$ 为 $0$，则 $(x_0, y)$ 必为 $0$，反之会出现更靠左上的 $\begin{pmatrix} 0 & 1 \\ 1 & ? \end{pmatrix}$ 结构；若 $(x_0', y)$ 为 $1$，则 $(x_0, y)$ 为 $0$ 或 $1$ 均可。
可以发现，必然有 $(x_0', y) \ge (x_0, y)$，这就说明 $p' \ge p$。
接下来，继续找到 $(x_0', y_0)$ 上方第一个 $1$，记其位置为 $(x_0'', y_0)$，标号为 $(p'', q'')$，类似的，有 $q'' = q'-1$ 且 $p'' \ge p'$。
重复上述过程，直到当前格子上方找不到任何 $1$，记当前格为 $(x_*, y_0)$，标号为 $(p_*, q_*)$，有 $p_* \ge p, q_* = 1$。
找到 $(x_*, y_0)$ 左方第一个 $1$，记其位置为 $(x_*, y_0')$，标号为 $p_*', q_*'$。
对 $p_*, p_*'$，显然有 $p_*' = p_*-1$。
对 $q_*, q_*'$，考察 $(x_*, y_0')$ 上方的格子 $(x, y_0')\ (x < x_*)$ 与 $(x_*, y_0)$ 上方对应的格子 $(x, y_0)$。
类似上面 $p, p'$ 的分析，可以说明 $(x, y_0') \ge (x, y_0)$，进而得到 $q_*' \ge q_*$。
重复上述过程，直到当前格子左方找不到任何 $1$，则标号的第 $1$ 维每次减小 $1$，第 $2$ 维单调不降。
持续向上或向左找点的过程，边界情况是，当前格子上方和左方都找不到任何 $1$，此时该格子标号为 $(1, 1)$。
对上述分析归纳，可得最靠左上时的推论：对初始格 $(x_0, y_0)$ (暂时视为 $1$) 的标号 $(p, q)$ 及任意 $1 \le p' \le p, 1 \le q' \le q$，必能在左上角为 $(1, 1)$，右下角为 $(x_0, y_0)$ 的子矩形内找到一个为 $1$ 的点，其标号为 $(p', q')$。
现在，我们把 $(x_0, y_0)$ 翻回 $0$，带来的影响是，$p' = p, q' = q$ (原来在 $(x_0, y_0)$ 取到) 现在取不到。
记 $(x_0, y_1)$ 的标号为 $(p', q')$，$(x_1, y_0)$ 的标号为 $(p'', q'')$，类似本部分第七 ~ 九行的分析，可以说明 $\begin{cases} p = p' \\ q \ge q' \end{cases}$ 且 $\begin{cases} p \ge p'' \\ q = q'' \end{cases}$。
若两个 $\ge$ 同时取等，则 $(x_0, y_1)$ 与 $(x_1, y_0)$ 的标号相同，不合法。
反之，必有至少 $1$ 个 $\ge$ 不取等，由最靠左上时的推论，也可以在左上角为 $(1, 1)$，右下角为 $(x_0, y_0)$ 的子矩形中找到一个标号相同的点。
综上，证毕。
可以发现，上述 "最靠左上的推论" 的证明过程中，"最靠左上" 的假设仅用来限制子矩形中 $\begin{pmatrix} 0 & 1 \\ 1 & ? \end{pmatrix}$ 的出现。
证明结论一后，$\begin{pmatrix} 0 & 1 \\ 1 & ? \end{pmatrix}$ 结构必然不能出现，于是该推论不再依赖于 "最靠左上" 的假设，可以将其推广。
推论一：对格子 $(x, y)$，将其视为 $1$，求出此时的标号 $(p, q)$，则对于任意 $1 \le p' \le p, 1 \le q' \le q$，必能在左上角为 $(1, 1)$，右下角为 $(x, y)$ 的子矩形内找到一个为 $1$ 的点，其标号为 $(p', q')$；特别的，若 $(x, y)$ 本来为 $0$，则将其翻回 $0$ 后，$p' = p, q' = q$ 取不到。
结论二：若含有 $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ 子矩阵，则原矩阵不合法。
考虑找到最靠左上的这样的子矩形，记对应的两行为 $x_0, x_1$，两列为 $y_0, y_1$。
尝试找到 $(x_1, y_0), (x_1, y_0+1), \cdots, (x_1, y_1-1)$ 中最靠右的 $1$，$(x_0, y_1), (x_0+1, y_1), \cdots, (x_1-1, y_1)$ 中最靠下的 $1$。
情况一：两边都找不到。
此时，记 $(x_0, y_0)$ 的标号为 $(p, q)$，$(x_1, y_1)$ 的标号为 $(p', q')$，考虑分析 $p, p'$ 的大小关系与 $q, q'$ 的大小关系。
对 $(x_0, y_0)$ 上方的点 $(x, y_0)\ (x < x_0)$，记 $(x_1, y_1)$ 上方对应的点为 $(x, y_1)$，可以发现 $(x, y_0) \ge (x, y_1)$。
由于 $(x_0+1, y_1), \cdots, (x_1-1, y_1)$ 都是 $0$，这些点不会对 $q'$ 造成贡献，$(x_1, y_1)$ 的 $1$ 的贡献与 $(x_0, y_0)$ 的 $1$ 的贡献抵消，因此有 $q \ge q'$。
类似的，也可以说明 $p \ge p'$。
结合推论一，必能在左上角为 $(1, 1)$，右下角为 $(x_0, y_0)$ 的子矩形内找到一个为 $1$ 的点，其标号为 $(p', q')$。
综上，原矩阵不合法。
情况二：有一边找不到。
不难发现两边是对称的，不妨设下方 $(x_1, y_0), (x_1, y_0+1), \cdots, (x_1, y_1-1)$ 均为 $0$。
考虑找到左方 $(x_0+1, y_0), (x_0+2, y_0), \cdots, (x_1, y_0)$ 中最靠下的 $1$。
若不存在，取 $(x_0, y_0)$ 为子矩形左上点，$(x_0, y_1)$ 为子矩形右上点，左方的 $0$ 为子矩形左下点，则右方 $(x_1, y_1)$ 上边的对应位置为 $0$。
此时，考虑 $(x_0, y_0)$ 的标号 $(p, q)$ 与 $(x_1, y_1)$ 的标号 $(p', q')$，类似情况一的分析，有 $p \ge p', q \ge q'$，可证不合法。
若存在，记这个 $1$ 的位置为 $(x_1', y_0)$，类似的，可以说明右方 $(x_1'+1, y_1), (x_1'+2, y_1), \cdots, (x_1-1, y_1)$ 也均为 $0$。
此时，考虑 $(x_1', y_0)$ 的标号与 $(x_1, y_1)$ 的标号，也可证不合法。
情况三：两边都能找到。
不妨设下方 $1$ 的位置为 $(x_1, y_1')$，右方 $1$ 的位置为 $(x_1', y_1)$。
考察 $(x_1', y_1')$，由于不能出现 $\begin{pmatrix} 0 & 1 \\ 1 & ? \end{pmatrix}$，其必然为 $1$。
考察 $(x_0, y_1')$，取 $(x_0, y_0), (x_0, y_1'), (x_1, y_0), (x_1, y_1')$ 构成的子矩形，由于不能出现更靠上的 $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$，其必然为 $1$。
类似的，考察 $(x_1', y_0)$，其也必然为 $1$。
此时，考虑 $(x_1', y_1')$ 与 $(x_1, y_1)$ 的标号，可证不合法。
综上，证毕。
结论三：若不存在形如 $\begin{pmatrix} 0 & 1 \\ 1 & ? \end{pmatrix}$ 和 $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ 的子矩形，则原矩阵合法。
考虑反证，若原矩阵不合法，则必然能找到这种结构。
取标号相同的两位置 $(x_0, y_0), (x_1, y_1)\ (x_0 < x_1)$ (显然不能有 $x_0 = x_1$ 或 $y_0 = y_1$ )，分讨 $y_0, y_1$ 的大小关系。
情况一：$y_0 < y_1$。
考察 $(x_0, y_1)$，若其为 $1$，则在 $(x_0, y_0), (x_0, y_1)$ 这组对应位置上 $(x_1, y_1)$ 的第二维标号多 $1$，需要在某组 $(x, y_0), (x, y_1)\ (x < x_0)$ 上补回来。
取 $(x, y_0), (x, y_1), (x_1, y_0), (x_1, y_1)$ 构成的子矩形，由于不能出现 $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$，$(x_1, y_0)$ 必然为 $1$。
因此，$(x_0, y_0), (x_1, y_0)$ 这组对应位置上 $(x_1, y_1)$ 的第一维标号多 $1$，需要在某组 $(x_0, y), (x_1, y)\ (y < y_0)$ 上补回来。
此时，由于不能出现 $\begin{pmatrix} 0 & 1 \\ 1 & ? \end{pmatrix}$ 和 $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$，$(x, y)$ 上怎么填都不合法。
综上，可以说明 $(x_0, y_1)$ 必为 $0$，类似的也可以说明 $(x_1, y_0)$ 也为 $0$，这样 $(x_0, y_0), (x_0, y_1), (x_1, y_0), (x_1, y_1)$ 就形成了 $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ 的结构。
情况二：$y_0 > y_1$。
考察 $(x_0, y_1)$，由于不能出现 $\begin{pmatrix} 0 & 1 \\ 1 & ? \end{pmatrix}$，其只能为 $1$，这样 $(x_0, y_1), (x_1, y_1)$ 这组对应位置上 $(x_0, y_0)$ 的第一维标号多 $1$。
容易说明，对 $(x_0, y_1)$ 左侧的对应位置 $(x_0, y), (x_1, y)\ (y < y_1)$，必有 $(x_0, y) \ge (x_1, y)$。
综上，$(x_0, y_0)$ 的第一维标号必然大于 $(x_1, y_1)$ 的第一维标号，不成立。
综上，证毕。
子矩形的结构是不利于快速 check 的，考虑找到一个等价的判据。
显然，将原矩阵的所有空行空列删除，不影响 $\begin{pmatrix} 0 & 1 \\ 1 & ? \end{pmatrix}$ 与 $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ 的存在性。以下默认所有空行空列已被删除。
结论四：不存在 $\begin{pmatrix} 0 & 1 \\ 1 & ? \end{pmatrix}$ 和 $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ 等价于能够找到位置 $(x, y)$，使得以 $(1, 1)$ 为左上角，$(x, y)$ 为右下角的矩形全 $1$，同时以 $(x+1, y+1)$ 为左上角，$(n, m)$ 为右下角的矩形全 $0$ ( $x = n$ 或 $y = m$ 时默认合法)，且剩余的两个子矩形区域内部合法。
首先，若能找到这样的 $(x, y)$，容易说明不存在 $\begin{pmatrix} 0 & 1 \\ 1 & ? \end{pmatrix}$ 和 $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$。
考虑证明，若不存在 $\begin{pmatrix} 0 & 1 \\ 1 & ? \end{pmatrix}$ 和 $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$，必能找到合法的 $(x, y)$。
首先，可以说明 $(1, 1)$ 必然为 $1$，反之，其右侧不能存在 $1$ (这样会导致 $(1, 1)$ 下方只能填 $0$，形成空列)，会形成空行。
类似的，可以说明第 $1$ 行的结构从左往右必然形如 $1, 1, \cdots, 1, 0, 0, \cdots, 0$，第 $1$ 列的结构从上往下也形如 $1, 1, \cdots, 1, 0, 0, \cdots, 0$。
记第 $1$ 行第一个 $0$ 所在列为 $y_0$，第 $1$ 列第一个 $0$ 所在行为 $x_0$。
由于不存在 $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$，以 $(x_0, y_0)$ 为左上角，$(n, m)$ 为右下角的子矩形内必然全为 $0$。
由于不存在空行，第 $2, 3, \cdots, y_0-1$ 列中必然有 $1$ 列，在第 $x_0+1, x_0+2, \cdots, n$ 行上存在 $1$，记满足条件的最靠左的列为 $y_0'$。
类似的，第 $2, 3, \cdots, x_0-1$ 行中必然有 $1$ 行，在第 $y_0+1, y_0+2, \cdots, m$ 列上存在 $1$，记满足条件的最靠上的行为 $x_0'$。
由于不存在 $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$，必有 $(x_0-1, y_0'), (x_0-2, y_0'), \cdots, (1, y_0')$ 均为 $1$，同理 $(x_0', y_0-1), (x_0', y_0-2), \cdots, (x_0', 1)$ 也均为 $1$。
分析第 $2, 3, \cdots, y_0'-1$ 列在第 $x_0'$ 行下方的格子，此时下方的 $0$ 可能向上 "捅进来"，记这些列中最靠上的 $0$ 所在行为 $x_0''$。
类似的，第 $2, 3, \cdots, x_0'-1$ 行右方的 $0$ 可能向左 "捅进来"，记这些行中最靠左的 $0$ 所在列为 $y_0''$。
容易用相同的方式说明，以 $(x_0'', y_0'')$ 为左上角，$(n, m)$ 为右下角的子矩形内必然全为 $0$。
换个方向做一遍，第 $y_0''-1, y_0''-2, \cdots, y_0'$ 列中必然有 $1$ 列，在第 $x_0''+1, x_0''+2, \cdots, n$ 行上存在 $1$ (反之，$(x_0', y_0')$ 为合法划分点)。
同理，第 $x_0''-1, x_0''-2, \cdots, x_0'$ 行中必然有 $1$ 行，在第 $y_0''+1, y_0''+2, \cdots, m$ 列上存在 $1$。
记满足条件的最靠右的列为 $y_0'''$，最靠下的行为 $x_0'''$。
取第 $1$ 列的 $0, 1$ 可以说明 $(x_0'', y_0''')$ 上方全是 $1$，取第 $1$ 行的 $0, 1$ 可以说明 $(x_0''', y_0'')$ 左方全是 $1$，那么它们包起来的部分也全是 $1$。
综上，可以得到，$(x_0''', y_0''')$ 为合法划分点，证毕。
此时，利用结论四，可以直接 DP，记 $f_{x_1, y_1, x_2, y_2}$ 表示以 $(x_1, y_1)$ 为左上角，$(x_2, y_2)$ 为右下角的子矩形的答案。
取子矩形内部一点，把子矩形切成四块，对应转移即可。时间复杂度 $O(n^6)$。
考虑优化，注意到在右方或下方拼接全 $0$ 的矩形并不会使答案变劣，于是可以默认 $(x_2, y_2)$ 为 $(n, m)$，缩减状态至 $2$ 维，时间复杂度 $O(n^4)$。
更进一步，找到第 $m, m-1, \cdots$ 列向上的极长连续 $0$ 段长度 $u_m, u_{m-1}, \cdots$。
从右往左，将每个 $u_i$ 对 $u_{i+1}$ $\text{chkmin}$，会形成阶梯状的全 $0$ 区域，可以发现，取区域内的点转移，必定不如取区域边界上的点转移优。
原因在于，我们希望取尽量少的左上部分的 $0$ 改成 $1$，这样这部分的贡献更优，子状态肯定也不劣 (因为可以在子状态再把 $0$ 改成 $1$ )。
综上，每列的转移点只有 $1$ 个，时间复杂度 $O(n^3)$。
细节上，全 $0$ 行和全 $0$ 列只对 "把 $0$ 改成 $1$ " 部分的贡献有影响，预处理右下角为 $(n, m)$ 的子矩形内的空行和空列个数即可。