問題一覧 > 通常問題

No.86 TVザッピング(2)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 67
作問者 : kmjpkmjp
1 ProblemId : 195 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:09

問題文

yuki君は旅行先でテレビを見ようとした。
旅行先のテレビのリモコンには、ボタンが縦\(N\)段、横\(M\)列の長方形状に計\(N\times M\)個並んでおり、それぞれを押すとテレビの表示が対応するチャンネルに切り替わる。
しかし、この地方のテレビでは視聴可能なチャンネルと視聴できないチャンネルとがあった。

yuki君は視聴可能なチャンネルだけをすべて巡回したくなった。
ただし、yuki君は旅行で疲れているので、複雑な順番でボタンを押したくない。
そこで、yuki君は以下のルールで順にボタンを押す事を考えた。

  • 最初は任意の視聴可能なチャンネルのボタンを押すことができる。そして次に押すボタンを上下左右いずれかに隣接するボタンのうちから１つ選択する。
  • 以降、隣接するボタンを順に押していく。その際、次に押すボタンは、前と同じ向きに移動した先にあるボタンか、向きを左に90度回転した先にあるボタンのいずれかを選択する。
    （たとえば、今押したボタンが１つ前に押したボタンの上にある場合、次に押せるのはもう１つ上にあるボタンか、左にあるボタンのどちらかである。）
  • 視聴できないチャンネルのボタンは押してはならない。
  • 視聴可能なチャンネルのボタンを全てちょうど１回ずつ押し、最後に最初に押したボタンを押す。（例外として、最初に押したボタンだけは最後と合わせ２回押してよい）

    • 入力として\(N\), \(M\), 各ボタンに対応するチャンネルの視聴可否が与えられたとき、上記ルールをすべて満たすボタンの押し順が存在するか答えよ。

    入力

    \(N\) \(M\)
\(A_1\)
\(A_2\)
...
\(A_N\)

    \(1 \le N, M \le 100\)
    ２行目以降N行続く\(A_i\)はM文字の文字列であり、'.'と'#'のみで構成される。
    \(A_i\)のj文字目が'.'である場合、リモコンの\(i\)段\(j\)列のボタンは視聴可能なチャンネルに対応する。
    \(A_i\)のj文字目が'#'である場合、リモコンの\(i\)段\(j\)列のボタンは視聴できないチャンネルに対応する。

    各テストケースには、視聴可能なチャンネルが必ず2個以上含まれている。

    出力

    ルールを満たすボタンの押し順が存在するなら"YES"、不可能なら"NO"を出力せよ。
    最後に改行を出力せよ。

    サンプル

    サンプル1
    入力
    3 4
....
.##.
....
    出力
    YES

    どのボタンから初めても、視聴可能なボタンを反時計まわりに回れば巡回可能である。

    サンプル2
    入力
    3 3
...
...
...
    出力
    NO

    サンプル3
    入力
    3 3
..#
...
...
    出力
    YES

    最初に真ん中のボタンを押し、次にその上のボタンを押し、その後反時計回りに順にボタンを押して真ん中に戻ることができる。
    他のボタンを最初に押してしまうと、元のボタンに戻ってこられない。

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