No.13 囲みたい!

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 174
作問者 : yuki2006yuki2006
4 ProblemId : 37 / 出題時の順位表
問題文最終更新日: 2018-05-20 23:42:22

問題文

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

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

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

入力

\(W\ H\)
\(M_{11}\ \dots\ M_{i1}\ \dots\ M_{W1}\)
\(M_{12}\ \dots\ M_{i2}\ \dots\ M_{W2}\)
\(\dots\)
\(M_{1j}\ \dots\ M_{ij}\ \dots\ M_{Wj}\)
\(\dots\)
\(M_{1H}\ \dots\ M_{iH}\ \dots\ M_{WH}\)

\(1\)行目には 横を表す\(W\ (1 \leq W \leq 100) \)と縦を表す\(H\ (1 \leq H \leq 100)\)数値が半角スペース区切りで与えられる。
\(2\)行目以降には、各行\(i\)列目\(j\)行目を表す数値\(M_{ij}\ (1 \leq M_{ij} \leq 1000)\)が半角スペース区切りで与えられる。

出力

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もしくは右上の雲マークをクリックしてアカウントを作成してください。