No.455 冬の大三角

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 102
作問者 : クレチークレチー / テスター : はむこはむこ

2 ProblemId : 1438 / 出題時の順位表

Note

この問題はAdvent Calendar Contest Advent Calendar 2016の6日目の問題として作られました。

問題文

12月のある日。ふと夜空を見上げると、満天の星が広がっていました。
Y君は、この中から「冬の大三角」を構成する3つの星を探しましたが、
最後の1つがなかなか見つかりません。

さて、ここでY君が見つけた2つの星のみが存在する、
縦 $H$、横 $W$ の夜空の状態が与えられます。
この夜空に、3つの星を結ぶと三角形になるような位置に星を1つ加えてください。
どのような形状の三角形でも正解となります。

追記:解は一つ以上存在することが保証されます。

補足

3つの星を結ぶと三角形になるとは、例えば次のような状態を指します。
※ '*' は星を、'-' は何もないことを表します。

---------*--
-*----------
------------
---------*--
*-----------
*-----------
------------
-*----------

3つの星が一直線上に存在している場合は、三角形になりません。

----*-------
----*-------
------------
----*-------
-*----------
----*-------
------------
----------*-

入力

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$

1行目に、夜空の縦方向の大きさ$\,H$、横方向の大きさ$\,W\,$が与えられます。
以下 $H$ 行に、長さ $W$ の文字列 $S_i$ としてY君が見た夜空の状態が与えられます。
$S_i$ は、星を表す '*' と、何もないことを表す '-' のみで構成されます。
なお、星は2つのみであることが保証されます。

  • $H,W$ は整数
  • $2 \le H,W \le 100$

出力

3つの星が三角形を作るような位置に星を1つ加えた夜空の状態を、
入力と同じように、$H$ 行の長さ $W$ の文字列として出力してください。
最後に改行してください。

サンプル

サンプル1
入力
4 10
----------
-------*--
--*-------
----------
出力
----------
-------*--
--*-------
-------*--

出力は一例です。

サンプル2
入力
6 2
--
*-
--
--
--
*-
出力
--
*-
-*
--
--
*-

細長いですが、三角形です。

サンプル3
入力
12 50
--------------------------------------------------
---------*----------------------------------------
--------------------------------------------------
-----------------------------------------*--------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
出力
--------------------------------------------------
---------*----------------------------------------
--------------------------------------------------
-----------------------------------------*--------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------*-----------------------------
--------------------------------------------------

提出ページヘ