AT_pakencamp_2025_day3_g Make T

有 $N \times N$ 个格点宇宙人，坐标 $(x, y)$ 均为 $0 \leq x, y < N$ 的整数，除此之外别无其他宇宙人。 总共有 $N^2$ 个宇宙人，每人都有 4 只手。若两名宇宙人之间的距离恰好为 $1$，则这两人可以牵手（即建立一条双向连接）。 起始时，部分宇宙人对已经牵好了手，状态如下给出： - 当 $A_{i,j}=1$ 时，位于 $(i, j)$ 的宇宙人与 $(i, j+1)$ 的宇宙人已牵手（$0 \leq i < N$, $0 \leq j < N-1$）。 - 当 $B_{i,j}=1$ 时，位于 $(i, j)$ 的宇宙人与 $(i+1, j)$ 的宇宙人已牵手（$0 \leq i < N-1$, $0 \leq j < N$）。 你可以进行 0 次或多次以下操作： - 选择一对距离恰好为 $1$ 的宇宙人，让他们牵手。 请你通过适当添加牵手，使**正好与其他 3 名宇宙人牵手的宇宙人数最大**。

输入通过标准输入给出，格式如下： > $N$ > $A_{0,0}\ A_{0,1}\ \dots\ A_{0,N-2}$ > $\vdots$ > $A_{N-1,0}\ A_{N-1,1}\ \dots\ A_{N-1,N-2}$ > $B_{0,0}\ B_{0,1}\ \dots\ B_{0,N-1}$ > $\vdots$ > $B_{N-2,0}\ B_{N-2,1}\ \dots\ B_{N-2,N-1}$

输出可以达到的恰好与其他 $3$ 名宇宙人牵手的宇宙人的最大数量。

### 公告 **本题的预期解答有误，实际上可能无法在合理时间内解决，非常抱歉。本题已被从 Universal Cup 移除。** 不过，如果加上「宇宙人必须至少与另外两名宇宙人牵手」的限制，是一道合理的题目。 ### 样例解释 1  图 1 左侧为样例的初始状态。如图所示，额外操作 12 次牵手后，总共有 8 名宇宙人正好与 3 名宇宙人牵手。这是可能达到的最大值，且方案最优。 ### 数据范围 - $2 \leq N \leq 500$ - $A_{i,j} \in \{0,1\}$（$0 \leq i < N,\ 0 \leq j < N-1$） - $B_{i,j} \in \{0,1\}$（$0 \leq i < N-1,\ 0 \leq j < N$） - 输入保证全为整数 由 ChatGPT 5 翻译