[COCI2017-2018#5] Spirale

题目描述

Little Stjepan often likes to go out with his friends and have fun in a popular nightclub in Zagreb. However, Stjepan sometimes drinks too much soda and gets light headed from all the sugar. Last night was an example of this, which is why Stjepan had the same image in his mind the whole time. It was a scribble of number spirals of some sort. Since he can’t quite remember what the image looked like, but can describe it, he is asking you to reconstruct it for him.

Stjepan recalls that the image was of the shape of a table consisting of numbers written in ​N rows and ​M columns. Also, he recalls that there were ​K spirals in that table. For each spiral, the starting position is known, as well as the direction it’s moving in, which can be clockwise and counter-clockwise. An example is shown in the images below. The spirals created Stjepan’s image in exactly $10^{100}$ steps in the following way: 1. Initially, the table is empty, and each spiral is in its own starting position. 2. In each following step, each spiral moves to its next position. It is possible that, at times, the spirals leave the boundaries of the table, but also to return within it. 3. After exactly $10^{100}$ steps, for each field in the table, the final value is the value of the earliest step in which one of the spirals touched that field.

题目翻译

Little Stjepan 经常喜欢和他的朋友一起出去玩，在一个受欢迎的夜总会玩得开心萨格勒布。然而，Stjepan 有时会喝太多苏打水，因此所有人都会头晕目眩糖。昨晚就是一个例子，这就是为什么 Stjepan 在他一直在想。它是某种数字螺旋的涂鸦。既然他不能非常记得图像的样子，但可以描述它，他要求你为他重建它。
Stjepan 回忆说，这张图片是一个表格的形状，由书写的数字组成N行和 M 列。此外，他还记得那张桌子上有 K 个螺旋。对于每个螺旋，起始位置是已知的，以及它移动的方向，可以是顺时针方向和逆时针。下图中显示了一个示例。创造的螺旋Stjepan 的图像在 $10^{100}$ 的步骤中按以下方式进行：
1. 最初，桌子是空的，每个螺旋都在自己的起始位置。
2. 在接下来的每一步中，每个螺旋都移动到下一个位置。有可能，在某次，螺旋离开桌子的边界，但也回到它里面。
3. 恰好经过 $10^{100}$ 步后，对于表中的每个字段，最终值是其中一个螺旋接触该领域的最早步骤。
顺逆如图： 1逆2顺

输入格式

The first line of input contains positive integers ​N , ​M (1 ≤ ​N , ​M ≤ 50) and ​K (1 ≤ ​K ≤ ​N *​M ). Each of the following ​K lines contains three positive integers ​$X_i$ , ​$Y_i$ and ​$T_i$ (1 ≤ ​X ≤ ​N , 1 ≤ ​Y ≤ M , 0 ≤ ​T ≤ 1), the starting position of the $i^{th}$ spiral and its direction (0 - clockwise, 1 - counter-clockwise). No two spirals will begin in the same field.

输出格式

You must output ​N lines with ​M numbers, representing the table after each spiral makes $10^{100}$ steps.（两个数字在同一格子，输出小的）

样例 #1

样例输入 #1

3 3 1
2 2 0

样例输出 #1

9 2 3
8 1 4
7 6 5

样例 #2

样例输入 #2

3 3 1
2 2 1

样例输出 #2

3 2 9
4 1 8
5 6 7

样例 #3

样例输入 #3

3 3 2
1 1 0
1 2 0

样例输出 #3

1 1 4
6 5 5
19 18 17

提示

In test cases worth 50% of total points, it will hold: ​N =​M i ​K =1 and ​$X_i$ =​$Y_i$ =$\lfloor\frac{N+1}{2}\rfloor$, i.e. ​$X_i$ and ​$Y_i$ will be equal to the integer division of ​N +1 with 2.

为简单起见，字母 A 被添加到第一个螺旋的数字中，字母 B 被添加到第一个螺旋的数字中来自第二个螺旋的数字。 仅显示了第一个螺旋的前 20 个步骤，以及第二个螺旋的 21 个步骤。 灰色的字段是桌面内的表，所有其他格子都是超出桌子的范围，但显示是为了说明螺旋线在桌子外移动的方式。