Copy of a Copy of a Copy

题意翻译

## 题目描述 给定一张 $n$ 行 $m$ 列的黑白图片（下标从 $1$ 开始），每一个单元格都被涂上了黑色或白色（$1$ 或者 $0$）。 我们对这张图片进行了若干次（可能为零次）操作，每一次操作都是下列两种之一： - 选择一个单元格，这个单元格不能在图片的边缘（即，单元格所在行不能是 $1$ 或 $n$ 行，所在列不能是 $1$ 或 $m$ 列），并且这个单元格被四个不同颜色的单元格包围（中间 $0$ 四周 $1$，反之亦然），将这个单元格涂成相反的颜色； - 复制一份当前图片。 两种操作不一定会交替进行。 给出你初始图片与 $k$ 份复制图片，一共 $k+1$ 份图片，这 $k+1$ 份图片是被随机打乱的。 你的任务是恢复操作的顺序。若有多种可能答案，只输出其中一个即可。 所有数据保证答案一定存在。 ## 输入格式 输入第一行包含三个整数 $n$、$m$ 以及 $k$（$3\le n，m\le 30$；$0\le k\le 100$），分别表示图片的行数、列数和复制图片的数量。 接下来 $k+1$ 行，每行一张图片，包括 $k$ 张复制图片和 $1$ 张初始图片，顺序是打乱的。 每张图片由 $n$ 行 $m$ 列组成，每个单元格都为 $0$ 或 $1$。每张图片之前都有一个空行。 ## 输出格式 输出第一行一个整数，表示初始图片是第几张。图片按其输入顺序分别编号 $1$ 至 $k+1$。 输出第二行一个整数 $q$，表示进行了多少次操作。 接下来 $q$ 行，每行对应一次操作，须按正确顺序输出操作。每个操作有题目描述中提到的两种类型： - $1\ x\ y$ 表示在坐标 $(x,y)$ 执行第一种操作； - $2\ i$ 表示复制一份当前图片，编号是 $i$。

题目描述

It all started with a black-and-white picture, that can be represented as an $ n \times m $ matrix such that all its elements are either $ 0 $ or $ 1 $ . The rows are numbered from $ 1 $ to $ n $ , the columns are numbered from $ 1 $ to $ m $ . Several operations were performed on the picture (possibly, zero), each of one of the two kinds: - choose a cell such that it's not on the border (neither row $ 1 $ or $ n $ , nor column $ 1 $ or $ m $ ) and it's surrounded by four cells of the opposite color (four zeros if it's a one and vice versa) and paint it the opposite color itself; - make a copy of the current picture. Note that the order of operations could be arbitrary, they were not necessarily alternating. You are presented with the outcome: all $ k $ copies that were made. Additionally, you are given the initial picture. However, all $ k+1 $ pictures are shuffled. Restore the sequence of the operations. If there are multiple answers, print any of them. The tests are constructed from the real sequence of operations, i. e. at least one answer always exists.

输入输出格式

输入格式

The first line contains three integers $ n, m $ and $ k $ ( $ 3 \le n, m \le 30 $ ; $ 0 \le k \le 100 $ ) — the number of rows and columns of the pictures and the number of copies made, respectively. Then $ k+1 $ pictures follow — $ k $ copies and the initial picture. Their order is arbitrary. Each picture consists of $ n $ lines, each consisting of $ m $ characters, each character is either $ 0 $ or $ 1 $ . There is an empty line before each picture.

输出格式

In the first line, print a single integer — the index of the initial picture. The pictures are numbered from $ 1 $ to $ k+1 $ in the order they appear in the input. In the second line, print a single integer $ q $ — the number of operations. Each of the next $ q $ lines should contain an operation. The operations should be listed in order they were applied. Each operation is one of two types: - $ 1 $ $ x $ $ y $ — recolor a cell $ (x, y) $ (the $ y $ -th cell in the $ x $ -th row, it should not be on the border and it should be surrounded by four cells of opposite color to itself); - $ 2 $ $ i $ — make a copy of the current picture and assign it index $ i $ (picture with index the $ i $ should be equal to the current picture). Each index from $ 1 $ to $ k+1 $ should appear in the output exactly once — one of them is the index of the initial picture, the remaining $ k $ are arguments of the operations of the second kind. If there are multiple answers, print any of them. The tests are constructed from the real sequence of operations, i. e. at least one answer always exists.

输入输出样例

输入样例 #1

3 3 1

010
111
010

010
101
010

输出样例 #1

2
2
1 2 2
2 1

输入样例 #2

4 5 3

00000
01000
11100
01000

00000
01000
10100
01000

00000
01010
10100
01000

00000
01000
10100
01000

输出样例 #2

3
5
1 2 4
2 2
2 4
1 3 2
2 1

输入样例 #3

5 3 0

110
010
001
011
001

输出样例 #3

1
0

题目大意：
一张黑白图片可以表示为一个 $n \times m$ 的矩阵，矩阵的每个元素要么是 $0$ 要么是 $1$。对这个图片进行了若干次操作，每次操作有两种可能：

1. 选择一个不在图片边缘的单元格（即单元格所在的行不是第 $1$ 行或第 $n$ 行，所在的列不是第 $1$ 列或第 $m$ 列），并且这个单元格被四个不同颜色的单元格包围（如果这个单元格是 $0$，则四个包围它的单元格是 $1$；反之亦然），然后将这个单元格涂成相反的颜色；
2. 复制当前的图片。

操作顺序可能是任意的，不一定是交替进行的。

题目给出 $k+1$ 张图片，包括 $k$ 张复制图片和 $1$ 张初始图片，这 $k+1$ 张图片的顺序是随机的。

需要恢复操作的顺序。如果有多种可能的答案，输出其中任意一个即可。保证至少存在一个答案。

输入输出数据格式：

输入格式：
- 第一行包含三个整数 $n$、$m$ 和 $k$（$3 \le n, m \le 30$；$0 \le k \le 100$），分别表示图片的行数、列数和复制图片的数量。
- 接下来 $k+1$ 行，每行一张图片，包括 $k$ 张复制图片和 $1$ 张初始图片，顺序是打乱的。
- 每张图片由 $n$ 行 $m$ 列组成，每个单元格都为 $0$ 或 $1$。每张图片之前都有一个空行。

输出格式：
- 第一行一个整数，表示初始图片是第几张。图片按其输入顺序分别编号 $1$ 至 $k+1$。
- 第二行一个整数 $q$，表示进行了多少次操作。
- 接下来 $q$ 行，每行对应一次操作，按正确顺序输出操作。每个操作有题目描述中提到的两种类型：
- $1\ x\ y$ 表示在坐标 $(x,y)$ 执行第一种操作；
- $2\ i$ 表示复制一份当前图片，编号是 $i$。

输入输出样例：

输入样例 #1：
```
3 3 1

010
111
010

010
101
010
```
输出样例 #1：
```
2
2
1 2 2
2 1
```

输入样例 #2：
```
4 5 3

00000
01000
11100
01000

00000
01000
10100
01000

00000
01010
10100
01000

00000
01000
10100
01000
```
输出样例 #2：
```
3
5
1 2 4
2 2
2 4
1 3 2
2 1
```

输入样例 #3：
```
5 3 0

110
010
001
011
001
```
输出样例 #3：
```
1
0
```

保证至少存在一个答案。题目大意： 一张黑白图片可以表示为一个 $n \times m$ 的矩阵，矩阵的每个元素要么是 $0$ 要么是 $1$。对这个图片进行了若干次操作，每次操作有两种可能： 1. 选择一个不在图片边缘的单元格（即单元格所在的行不是第 $1$ 行或第 $n$ 行，所在的列不是第 $1$ 列或第 $m$ 列），并且这个单元格被四个不同颜色的单元格包围（如果这个单元格是 $0$，则四个包围它的单元格是 $1$；反之亦然），然后将这个单元格涂成相反的颜色； 2. 复制当前的图片。 操作顺序可能是任意的，不一定是交替进行的。 题目给出 $k+1$ 张图片，包括 $k$ 张复制图片和 $1$ 张初始图片，这 $k+1$ 张图片的顺序是随机的。 需要恢复操作的顺序。如果有多种可能的答案，输出其中任意一个即可。保证至少存在一个答案。 输入输出数据格式： 输入格式： - 第一行包含三个整数 $n$、$m$ 和 $k$（$3 \le n, m \le 30$；$0 \le k \le 100$），分别表示图片的行数、列数和复制图片的数量。 - 接下来 $k+1$ 行，每行一张图片，包括 $k$ 张复制图片和 $1$ 张初始图片，顺序是打乱的。 - 每张图片由 $n$ 行 $m$ 列组成，每个单元格都为 $0$ 或 $1$。每张图片之前都有一个空行。 输出格式： - 第一行一个整数，表示初始图片是第几张。图片按其输入顺序分别编号 $1$ 至 $k+1$。 - 第二行一个整数 $q$，表示进行了多少次操作。 - 接下来 $q$ 行，每行对应一次操作，按正确顺序输出操作。每个操作有题目描述中提到的两种类型： - $1\ x\ y$ 表示在坐标 $(x,y)$ 执行第一种操作； - $2\ i$ 表示复制一份当前图片，编号是 $i$。 输入输出样例： 输入样例 #1： ``` 3 3 1 010 111 010 010 101 010 ``` 输出样例 #1： ``` 2 2 1 2 2 2 1 ``` 输入样例 #2： ``` 4 5 3 00000 01000 11100 01000 00000 01000 10100 01000 00000 01010 10100 01000 00000 01000 10100 01000 ``` 输出样例 #2： ``` 3 5 1 2 4 2 2 2 4 1 3 2 2 1 ``` 输入样例 #3： ``` 5 3 0 110 010 001 011 001 ``` 输出样例 #3： ``` 1 0 ``` 保证至少存在一个答案。