UOJ Logo

NOI.AC

1S 512MB

#102. 棋盘

统计

题目描述

​ 老虎和蒜头是好朋友。

​ 老虎有一张 $ n \times m $ 的棋盘,棋盘上的一些位置放了棋子,我们用 # 表示棋子,. 表示空格。接下来蒜头会进行一些操作:

  1. 蒜头找到了两个格子 $ (x, b) $ 和 $ (x, c) $ 中有棋子 $(b < c)$, $ b $ 和 $ c $ 奇偶性相同,且对于任意 $ b < y < c $ 来说,在格子 $ (x, y) $ 处均不存在棋子,那么蒜头会在 $ (x, \frac{b + c}{2}) $ 放一枚棋子,并结束这次操作。

  2. 蒜头找到了两个格子 $ (b, y) $ 和 $ (c, y) $ 中有棋子 $(b < c)$, $ b $ 和 $ c $ 奇偶性相同,且对于任意 $ b < x < c $ 来说,在格子 $ (x, y) $ 处均不存在棋子,那么蒜头会在 $ (\frac{b + c}{2}, y) $ 放一枚棋子,并结束这次操作。

    蒜头会随机进行这些操作,直到没有操作可以执行为止,现在蒜头想要知道一种可能的操作序列。

输入格式

​ 第一行输出两个正整数 $ n $ 和 $ m $ ,表示棋盘的大小。

​ 接下来 $ n $ 行,每行 $ m $ 个字符,表示初始的棋盘状态。

输出格式

​ 输出的第一行应当包含一个整数 $ k $ ,表示操作序列的长度 $ k $。

​ 接下来的 $ k $ 行,每行包括四个整数 1 x b c 或是 2 y b c ,表示这一次的操作。

​ 你需要保证在进行了 $ k $ 次操作后不能再进行任何其他的操作,否则你的输出将会被判定为 Wrong Answer

样例

样例一

input

4 5
#...#
....#
..#..
...#.

output

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

explanation

最终的棋盘状态为:

#516#
..23#
..#4.
...#.

其中数字 $ i $ 表示第 $ i $ 次操作时被放置上的棋子。

数据范围及限制

对于 100% 的数据,$ n, m \le 1500 $ 。

对于 30% 的数据,$ n, m \le 50 $ 。

对于 60% 的数据,$ n, m \le 300 $ 。

时间限制: 2s

空间限制: 512MB

样例数据下载