P1363 Illusion Maze

(The cat-people LHX and WD joined forces to repel the dog-people’s invasion. Unfortunately, before retreating, the dog-people created an illusion maze for them.) WD: Boo-hoo, what should we do... LHX: Momo... We can definitely get out! WD: Mm, +U+U!

The illusion maze can be regarded as infinite, but it is formed by repeating several $N \times M$ matrices. In the matrix, some cells are roads, denoted by \verb!.!, and some cells are walls, denoted by \verb!#!. The position of LHX and WD is denoted by \verb!S!. That is, for a point $(x,y)$ in the maze, if $(x \bmod n,y \bmod m)$ is \verb!.! or \verb!S!, then this location is a road; if $(x \bmod n,y \bmod m)$ is \verb!#!, then this location is a wall. LHX and WD can move in the four directions up, down, left, and right, and of course they cannot move into walls. Here, $n$ and $m$ refer to $N$ and $M$ respectively. Please tell LHX and WD whether they can escape from the illusion maze (if they can reach positions at unbounded distance from the starting point, we consider that they can escape). Otherwise, LHX will have to activate the castle’s self-destruction program... but he really does not want to do that unless absolutely necessary.

The input contains multiple test cases. For each test case, the first line contains two integers $N, M$. Then follows an $N \times M$ character matrix, representing the cells from $(0,0)$ to $(n-1,m-1)$.

For each test case, output a string, "Yes" or "No".

- For 30% of the testdata, $1 \le N, M \le 20$. - For 50% of the testdata, $1 \le N, M \le 100$. - For 100% of the testdata, $1 \le N, M \le 1500$, with no more than $10$ test cases per test point. Translated by ChatGPT 5