G - Snake Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

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}) は辺を共有して隣接している

マス目上のどのマスをヘビが占領しているかが与えられます。具体的には、ある整数 i (1 \le i \le k) が存在して (x_i, y_i) = (a, b) であるならば、 S_{a, b} は # であり、そうでないなら . です。
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} は # または .
  • 問題文の状況と合致する 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}

出力

まず 1 行目に k を出力せよ。
次に 2 行目から 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

Score : 6 points

Warning

Do not make any mention of this problem until December 27, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a grid S with H rows and W columns of squares. Let Square (i, j) denote the square at the i-th row from the top and j-th column from the left.
There is a snake on this grid. Its position is represented by a positive integer k and a sequence of k pairs of coordinates (x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_k, y_k) satisfying the following conditions:

  • 1 \le x_i \le H;
  • 1 \le y_i \le W;
  • (x_i, y_i) \neq (x_j, y_j) (i \neq j);
  • Square (x_i, y_i) and Square (x_{i + 1}, y_{i + 1}) are adjacent, sharing an edge.

You are given the set of squares occupied by the snake. More specifically, S_{a, b} is # if there is an integer i (1 \le i \le k) such that (x_i, y_i) = (a, b), and S_{a, b} is . otherwise.
Find one possible combination of k and the sequence (x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_k, y_k).

Constraints

  • 1 \le H \le 4
  • 1 \le W \le 4
  • S_{i, j} is # or ..
  • There exist an integer k and a sequence (x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_k, y_k) that are consistent with the situation.

Input

Input is given from Standard Input in the following format:

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}

Output

In the first line, print the integer k.
In each of the second through (k + 1)-th lines, print the coordinates; the (1 + i)-th line should contain x_i and y_i with a space in between.
Any combination of an integer and a sequence of coordinates that satisfies the condition will be accepted.

Sample Input 1

3 3
##.
.##
###

Sample Output 1

7
1 1
1 2
2 2
2 3
3 3
3 2
3 1

The reversal of this sequence will also be accepted.

Sample Input 2

3 4
####
####
.#..

Sample Output 2

9
1 4
2 4
2 3
1 3
1 2
1 1
2 1
2 2
3 2

There are also solutions other than this and its reversal.

Sample Input 3

3 3
.##
###
###

Sample Output 3

8
1 2
1 3
2 3
2 2
2 1
3 1
3 2
3 3