分数: 6 点
警告
2020 年 12 月 27 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
我们有一个网格 S 与 H 行和 W 方格列。让广场 (i, j) 表示 i从顶部开始的第行和 j左起第 列。
该网格上有一条蛇。它的位置用正整数表示 k 和一系列 k 坐标对 (x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_k, y_k) 满足以下条件:
- 1 \le x_i \le H;
- 1 \le y_i \le W;
- (x_i, y_i) \neq (x_j, y_j) (i \neq j);
- 广场 (x_i, y_i) 和广场 (x_{i + 1}, y_{i + 1}) 相邻,共享一条边。
给你一组被蛇占据的方格。 更具体地说, S_{a, b} is # 如果有一个整数 i (1 \le i \le k) 这样 (x_i, y_i) = (a, b),和 S_{a, b} is . 否则。
找到一种可能的组合 k 和序列 (x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_k, y_k).
约束
- 1 \le H \le 4
- 1 \le W \le 4
- S_{i, j} is
#or.. - 存在一个整数 k 和一个序列 (x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_k, y_k) 表示与情况相符。
输入
输入由标准输入按以下格式给出:
H W
S_{1, 1}S_{1, 2}S_{1, 3} \dots S_{1, W}
S_{2, 1}S_{2, 2}S_{2, 3} \dots S_{2, W}
S_{3, 1}S_{3, 2}S_{3, 3} \dots S_{3, W}
\hspace{40pt} \vdots
S_{H, 1}S_{H, 2}S_{H, 3} \dots S_{H, W}
输出
在第一行中,打印整数 k.
在每一秒到 (k + 1)第行,打印坐标;的 (1 + i)- 第行应包含 x_i 和 y_i 之间有一个空格。
满足条件的整数和坐标序列的任何组合都将被接受。
示例输入 1
3 3 ##. .## ###
示例输出 1
7 1 1 1 2 2 2 2 3 3 3 3 2 3 1
此顺序的颠倒也将被接受。
示例输入 2
3 4 #### #### .#..
示例输出 2
9 1 4 2 4 2 3 1 3 1 2 1 1 2 1 2 2 3 2
除了这个及其逆转之外,还有其他解决方案。
示例输入 3
3 3 .## ### ###
示例输出 3
8 1 2 1 3 2 3 2 2 2 1 3 1 3 2 3 3