← 返回题目列表

AtCoder · past202012_g

G. 蛇

中文机器翻译题面 查看原题

分数: 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