問題一覧 > 通常問題

No.13 囲みたい!

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 251
作問者 : yuki2006yuki2006
6 ProblemId : 37 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-05-20 23:42:22

問題文

kevinはとあるゲームをしている。
WH個のマスで構成されるフィールドが与えられる。
最初にあるマスを選択し、上下左右の同じ数字のみ辿れ、任意の場所で離す事ができる。
この時、同じ数字のみをたどって、囲みができたら高得点になるゲームである。

囲みとは、辿ったマスの順番に線をつないだ時に、K(4)角形ができていることである。

フィールドが与えられた時に囲みができるかどうか判定してください。
囲みが出来る場合 possible 出来ない場合は impossible を出力してください。

入力

W H
M11  Mi1  MW1
M12  Mi2  MW2

M1j  Mij  MWj

M1H  MiH  MWH

1行目には 横を表すW (1W100)と縦を表すH (1H100)数値が半角スペース区切りで与えられる。
2行目以降には、各行i列目j行目を表す数値Mij (1Mij1000)が半角スペース区切りで与えられる。

出力

possible または impossible を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3 3
1 2 3
1 1 3
1 1 4
出力
possible

左下で1をうまくたどると、4角形ができます。

サンプル2
入力
5 4
1 2 2 2 3
2 2 4 2 2
2 1 1 1 2
2 2 2 2 2
出力
possible

2で凸の8角形ができる。

サンプル3
入力
5 4
5 5 5 3 5
5 3 1 5 1
5 2 2 5 8
5 5 5 5 9
出力
impossible

このフィールドでは囲みが出来ない。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。