网版绕中心旋转 180∘ 后,格子 (i,j)(0-下标)映到 (n−1−i,m−1−j)。只能把 o 改成 p,因此一对不同字符必然是一 o 一 p,改一次即可对齐;相同则无需操作。中心格(n、m 均为奇数时)映到自身,不必改。
枚举所有互为对称的格子对(只处理字典序较小的一侧以免重复),不同则答案加一。
时间复杂度 O(nm),空间复杂度 O(nm)。
印花车间有一块 n 行 m 列的网版,每个格子是字符 o 或 p:o 表示尚未固色,p 表示已经固色。一次操作可以把任意一个 o 改成 p(不能把 p 改回 o)。成品要求网版中心对称:绕中心旋转 180∘ 后必须与原网版完全相同。
也就是说,对所有位置 (i,j)(行、列均从 1 编号),格子 (i,j) 与格子 (n+1−i,m+1−j) 上的字符相同。
求使网版变成中心对称所需的最少操作次数。
约束:1≤n,m≤103。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册