問題一覧 > 通常問題

No.86 TV Zapping (2)

レベル : / AI推定難易度 : 1725 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 67
作問者 : 👑 kmjp
お気に入りにしたユーザー ProblemId : 195 / 自分の提出
問題文最終更新日: 2026-06-25 04:34:36
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 61 (順位表) の他の問題:

Problem Statement

yuki-kun tried to watch TV at his travel destination.
The remote control of the TV there has a total of \(N\times M\) buttons arranged in a rectangle of \(N\) rows and \(M\) columns, and pressing each button switches the TV display to the corresponding channel.
However, on TVs in this region, some channels are watchable and others are not.

yuki-kun wants to cycle through all of the watchable channels and only those.
However, yuki-kun is tired from his trip, so he does not want to press the buttons in a complicated order.
He therefore decided to press the buttons in order according to the following rules.

  • At first, he may press the button of any watchable channel. Then, he chooses the next button to press from among the buttons adjacent to it above, below, left, or right.
  • After that, he presses adjacent buttons one after another. When doing so, the next button to press is chosen as either the button reached by moving in the same direction as before, or the button reached after rotating the direction 90 degrees to the left.
    (For example, if the button just pressed is above the button pressed immediately before it, the next button he can press is either the button one further above or the button to the left.)
  • He must not press a button of an unwatchable channel.
  • He presses every button of a watchable channel exactly once, and finally presses the button he pressed first. (As an exception, only the button pressed first may be pressed twice, counting the final press.)

    • Given as input \(N\), \(M\), and whether the channel corresponding to each button is watchable, determine whether there exists an order of pressing the buttons that satisfies all of the above rules.

    Input

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

    \(1 \le N, M \le 100\)
    Each \(A_i\), given over the N lines from the second line onward, is a string of M characters consisting only of '.' and '#'.
    If the j-th character of \(A_i\) is '.', the button at row \(i\), column \(j\) of the remote control corresponds to a watchable channel.
    If the j-th character of \(A_i\) is '#', the button at row \(i\), column \(j\) of the remote control corresponds to an unwatchable channel.

    Each test case is guaranteed to contain at least 2 watchable channels.

    Output

    Output "YES" if there exists an order of pressing the buttons that satisfies the rules, and "NO" otherwise.
    Print a newline at the end.

    Sample

    Sample 1
    Input
    3 4
....
.##.
....
    Output
    YES

    Whichever button he starts from, he can cycle through the watchable buttons by going around counterclockwise.

    Sample 2
    Input
    3 3
...
...
...
    Output
    NO

    Sample 3
    Input
    3 3
..#
...
...
    Output
    YES

    He can first press the middle button, then the button above it, and then press the buttons in order counterclockwise to return to the middle.
    If he presses any other button first, he cannot return to the original button.

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