网格图染色问题
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
Doesn't have.
题目描述
- 有一个 行 列网格图,每个位置要么是黑色,要么是白色。
- 网格图第 行第 列的颜色用 表示,具体地, 表示白色, 表示黑色。
- 定义一次操作:
- 说人话:
- 你选择网格图的某一行,并将这一行复制一份,拿在手上,
- 你将这一行顺时针旋转 ,
- 你选择网格图的某一列,并用手里的格子将其覆盖。
- 形式化地:
- 你选择 满足 ,
- 对每个 ,设 ,
- 对每个 , 的值会变为 。
- 说人话:
- 你的目标是把整个网格图都变为黑色并最小化操作次数。
- 数据保证存在至少一种构造方案。
输入格式
从 color.in
读入。
- 第一行一个整数 ,
- 接下来 行,第 行 个整数,表示 。
输出格式
输出到 color.out
。
- 输出一行一个整数,表示最小操作次数,
输入输出样例
2
0 1
1 0
3
样例解释
一种可能的操作过程如下: 第一次操作,选择 :
00
11
第二次操作,选择 :
10
11
第三次操作,选择 :
11
11
可以证明不存在更优方案。
数据范围
子任务
子任务编号 | 分值 | 限制 |
---|---|---|
1 | 40 | 至少存在一个全黑的行,即 |
2 | 每列都至少存在一个黑色格子,即 | |
3 | 20 | N/A |
- 大样例下载
- 编号为 的大样例满足编号为 的子任务的限制