B. 网格图染色问题

    传统题 文件IO:color 1000ms 256MiB

网格图染色问题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

Doesn't have.

题目描述

  • 有一个 nnnn 列网格图,每个位置要么是黑色,要么是白色。
  • 网格图第 ii 行第 jj 列的颜色用 ai,ja_{{i,j}} 表示,具体地,ai,j=0a_{i,j}=0 表示白色,ai,j=1a_{i,j}=1 表示黑色。
  • 定义一次操作:
    • 说人话:
      • 你选择网格图的某一行,并将这一行复制一份,拿在手上,
      • 你将这一行顺时针旋转 90°90°
      • 你选择网格图的某一列,并用手里的格子将其覆盖。
    • 形式化地:
      • 你选择 i,ji,j 满足 1in,1jn1\le i\le n,1\le j\le n
      • 对每个 1kn1\le k\le n,设 pk=ai,kp_k=a_{i,k}
      • 对每个 1kn1\le k\le nak,ja_{k,j} 的值会变为 pkp_k
  • 你的目标是把整个网格图都变为黑色并最小化操作次数。
  • 数据保证存在至少一种构造方案。

输入格式

color.in 读入。

  • 第一行一个整数 nn
  • 接下来 nn 行,第 iinn 个整数,表示 ai,ja_{i,j}

输出格式

输出到 color.out

  • 输出一行一个整数,表示最小操作次数,

输入输出样例

2
0 1
1 0
3

样例解释

一种可能的操作过程如下: 第一次操作,选择 i=1,j=2i=1,j=2

00
11

第二次操作,选择 i=2,j=1i=2,j=1

10
11

第三次操作,选择 i=2,j=2i=2,j=2

11
11

可以证明不存在更优方案。

数据范围

  • n103n\leq 10^3

子任务

子任务编号 分值 限制
1 40 至少存在一个全黑的行,即  i,ai,j=1\exists~i,a_{i,j}=1
2 每列都至少存在一个黑色格子,即  j, i,ai,j=1\forall~j,\exists~i,a_{i,j}=1
3 20 N/A
  • 大样例下载
  • 编号为 ii 的大样例满足编号为 ii 的子任务的限制

24KOI 2025 体验赛 No.4

未参加
状态
已结束
规则
OI
题目
4
开始于
2025-6-22 13:00
结束于
2025-6-22 16:30
持续时间
3.5 小时
主持人
参赛人数
33