正方形のマスが縦に 行、横に 列並んでできた長方形のフィールドがあります。正方形のマスの一辺の長さは です。上から 行目、左から 列目のマスをマス と呼ぶことにします。
フィールドの各マスには状態があり、マス の状態は文字 で与えられます。文字 は .
または #
のいずれかです。
最初、マス に直径が の円の形をした板がマスに内接して置かれています。この板を、板が置かれているマスと辺で隣接したマスへ移動させる(縦または横の辺と平行に動かして、隣接するマスに内接させる)ことを繰り返してマス へ移動させたいです。ただし、 が #
であるマス を通ることはできません。
考えられる板の動かし方のうち、板が掃く面積 (画像を参考にしてください) が最小となるときについて、板が掃く面積を求めて以下で指定する書式で出力してください。
.
または #
.
入力は標準入力から以下の形式で与えられます。
各マスの状態によっては板をマス からマス まで移動させられません。そのような場合、以下のように と出力してください。
-1
そうでない場合、板が掃く面積は非負整数 と円周率 を用いて と表現できます。 が整数のときは として、そうでないときは が既約分数になるように を選び、 を順番に以下のように出力してください。
a b c
3 3 .## ... ##.
14 3 2
問題文中の画像で示したものと同一の経路で板を動かすしかありません。このとき、板が掃く面積は となります。
1 1 .
0 1 1
このとき板ははじめから目的地にいますが、経路の始点や終点で板が占めている面積も板が掃く面積であるとみなします。このとき板が掃く面積は です。
5 5 ....# ...#. ..#.. .#... #....
-1
条件を満たす経路が存在しない場合もあります。