lazy robotic vacuum cleaner

2 secs 1024 MB
naskya's icon naskya

問題

正方形のマスが縦に HH 行、横に WW 列並んでできた長方形のフィールドがあります。正方形のマスの一辺の長さは 22 です。上から ii 行目、左から jj 列目のマスをマス (i,j)(i, j) と呼ぶことにします。

フィールドの各マスには状態があり、マス (i,j)(i, j)状態は文字 Si,jS_{i, j} で与えられます。文字 Si,jS_{i, j}. または # のいずれかです。

最初、マス (1,1)(1, 1) に直径が 22 の円の形をした板がマスに内接して置かれています。この板を、板が置かれているマスと辺で隣接したマスへ移動させる(縦または横の辺と平行に動かして、隣接するマスに内接させる)ことを繰り返してマス (H,W)(H, W) へ移動させたいです。ただし、Si,jS_{i, j}# であるマス (i,j)(i, j) を通ることはできません。

考えられる板の動かし方のうち、板が掃く面積 (画像を参考にしてください) が最小となるときについて、板が掃く面積を求めて以下で指定する書式で出力してください。

参考画像

制約

  • 1H1001 \leq H \leq 100
  • 1W1001 \leq W \leq 100
  • Si,jS_{i, j}. または #
  • S1,1S_{1, 1}SH,WS_{H, W} はともに .

入力

入力は標準入力から以下の形式で与えられます。

H WH \ W\\ S1,1S1,2 S1,WS_{1,1} \hspace{0.5em} S_{1,2} \hspace{0.5em} \cdots \ S_{1,W}\\ S2,1S2,2 S2,WS_{2,1} \hspace{0.5em} S_{2,2} \hspace{0.5em} \cdots \ S_{2,W}\\ \hspace{0.75em} \vdots \hspace{1.75em} \vdots \hspace{3.75em} \vdots\\ SH,1 SH,2  SH,WS_{H,1} \ S_{H,2} \ \cdots \ S_{H,W}

出力

各マスの状態によっては板をマス (1,1)(1, 1) からマス (H,W)(H, W) まで移動させられません。そのような場合、以下のように 1-1 と出力してください。

-1

そうでない場合、板が掃く面積は非負整数 a,b,ca, b, c と円周率 π\pi を用いて a+bcπa + \frac{b}{c} \pi と表現できます。bc\frac{b}{c} が整数のときは c=1c = 1 として、そうでないときは bc\frac{b}{c} が既約分数になるように b,cb, c を選び、a,b,ca, b, c を順番に以下のように出力してください。

a b c

サンプル

入力例1
3 3
.##
...
##.
出力例1
14 3 2

問題文中の画像で示したものと同一の経路で板を動かすしかありません。このとき、板が掃く面積は 14+32π14 + \frac{3}{2} \pi となります。


入力例2
1 1
.
出力例2
0 1 1

このとき板ははじめから目的地にいますが、経路の始点や終点で板が占めている面積も板が掃く面積であるとみなします。このとき板が掃く面積は 0+11π0 + \frac{1}{1} \pi です。


入力例3
5 5
....#
...#.
..#..
.#...
#....
出力例3
-1

条件を満たす経路が存在しない場合もあります。

Submit


Go (1.21)