P3877 [TJOI2010] Cleaning the Room

A new batch of dormitories has been built at the school, and the student on duty, Xiao A, needs to clean all empty rooms. The layout of these dormitories is unusual: all rooms in the building form an $N \times M$ grid. Each room has a door on each of its north, south, east, and west walls leading to the adjacent room. Some rooms are used for storage and do not need to be cleaned. Xiao A wants to design several cleaning routes such that each room that needs cleaning is entered and exited exactly once, and the same door must not be used to both enter and leave that room. Each route must be a closed cycle, and each route must pass through more than 2 rooms. As shown in the two figures below, both are valid cleaning plans (gray cells are rooms used for storage):  Xiao A finds that for certain layouts, no plan satisfying the requirements exists. He asks you to write a program to determine, for a given room layout, whether a valid plan exists.

The first line contains an integer $T$ ($1 \le T \le 10$), indicating that there are $T$ groups of testdata in the file. Then follow the descriptions of the $T$ groups of testdata. For each group, the first line contains two integers $N$ and $M$. The next $N$ lines each contain $M$ characters describing a room layout. A '.' means the room needs cleaning; a '#' means the room is used for storage and does not need cleaning.

Output $T$ lines. For each group, output one line, either "YES" or "NO", indicating whether such a cleaning plan exists.

- For 50% of the testdata, $3 \le N, M \le 12$. - For 100% of the testdata, $3 \le N, M \le 30$. - Time limit per test point: 1 second. Translated by ChatGPT 5