A7361. [COCI 2024/2025 #3] 涂矩阵 / Bojanje
编程题
普及+/提高
知识点
题目描述
有一个初始为全白的 $n\times n$ 矩阵。
每次操作可以选择一列或者一行，将这一列或者这一行覆盖成红色或者蓝色。
给定矩阵的目标状态，请你构造一组操作序列，使得矩阵达到目标状态，或者报告无解。
不需要最小化操作序列的长度，只需要构造出合法方案即可。
每次操作可以选择一列或者一行，将这一列或者这一行覆盖成红色或者蓝色。
给定矩阵的目标状态，请你构造一组操作序列，使得矩阵达到目标状态，或者报告无解。
不需要最小化操作序列的长度，只需要构造出合法方案即可。
输入格式
第一行，一个正整数 $n$。
接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个整数 $a_{i,j}$ 描述目标状态中第 $i$ 行第 $j$ 列格子的颜色：
$0$ 表示白色。
$1$ 表示红色。
$2$ 表示蓝色。
接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个整数 $a_{i,j}$ 描述目标状态中第 $i$ 行第 $j$ 列格子的颜色：
$0$ 表示白色。
$1$ 表示红色。
$2$ 表示蓝色。
输出格式
如果无解，输出 $-1$。
否则，第一行输出一个整数 $k$，表示操作序列长度。
你需要保证 $0\le k\le 4000$。
接下来 $k$ 行，每行三个正整数 $a,b,c$，依次描述一次操作：
$a\in\{1,2\}$。
$a=1$ 表示选择的是行。
$a=2$ 表示选择的是列。
$1\le b\le n$，表示选择的是第 $b$ 行或者第 $b$ 列。
$c\in\{1,2\}$。
$c=1$ 表示涂成红色。
$c=2$ 表示涂成蓝色。
否则，第一行输出一个整数 $k$，表示操作序列长度。
你需要保证 $0\le k\le 4000$。
接下来 $k$ 行，每行三个正整数 $a,b,c$，依次描述一次操作：
$a\in\{1,2\}$。
$a=1$ 表示选择的是行。
$a=2$ 表示选择的是列。
$1\le b\le n$，表示选择的是第 $b$ 行或者第 $b$ 列。
$c\in\{1,2\}$。
$c=1$ 表示涂成红色。
$c=2$ 表示涂成蓝色。
输入输出样例
输入 #1
3 0 0 1 1 1 1 0 0 1
输出 #1
2 2 3 1 1 2 1
输入 #2
3 1 1 2 2 1 1 2 1 1
输出 #2
-1
输入 #3
4 0 1 2 1 2 2 2 1 0 1 2 1 1 1 2 1
输出 #3
5 2 2 1 1 2 2 2 4 1 1 4 1 2 3 2
说明/提示
## 数据范围
对于 $100\%$ 的数据：
$1\le n\le 2000$
$0\le a_{i,j}\le 2$
输出操作数需要满足：
$0\le k\le 4000$
## 子任务
| 子任务编号 | $n\le$ | 特殊性质 | 得分 |
| :--: | :--: | :--: | :--: |
| $1$ | $2000$ | 特殊性质 A | $15$ |
| $2$ | $100$ | 无 | $35$ |
| $3$ | $2000$ | 无 | $40$ |
特殊性质 A：$a_{i,j}\in\{0,1\}$。
对于 $100\%$ 的数据：
$1\le n\le 2000$
$0\le a_{i,j}\le 2$
输出操作数需要满足：
$0\le k\le 4000$
## 子任务
| 子任务编号 | $n\le$ | 特殊性质 | 得分 |
| :--: | :--: | :--: | :--: |
| $1$ | $2000$ | 特殊性质 A | $15$ |
| $2$ | $100$ | 无 | $35$ |
| $3$ | $2000$ | 无 | $40$ |
特殊性质 A：$a_{i,j}\in\{0,1\}$。