시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 62 7 2 100.000%

문제

재민이는 퍼즐게임 앱을 개발하였다.

격자에 공이 놓여있다. 공을 상하좌우 중 한 방향으로 이동시킬 수 있고, 이 때 공은 벽에 부딪히거나 격자의 끝에 도달할 때까지 그 방향으로 굴러간다. 특정 칸에는 별이 놓여 있고, 공이 그 칸에 멈추거나 그 칸을 지나가면 사용자는 그 별을 얻게 된다. 목표는 격자에 있는 모든 별을 얻는 것이다.

이 앱에는 레벨 에디터가 있어서 사용자가 자신만의 레벨을 만들고 공유할 수 있다. 어느 날 재민이는 “만든 레벨이 해결 가능한 레벨인지 검사하는 기능을 만들어 주세요!”라는 건의사항을 받았다. 글쎄, 말이야 쉽지만...

입력

첫 번째 줄에 격자의 높이 $H$와 너비 $W$가 주어진다. ($1 \leq H, W \leq 50$) 다음 $H$줄에는 격자의 각 행을 나타내는 길이 $W$의 문자열이 차례대로 주어진다. "#"은 벽, "."은 공간, "O"는 공, "*"는 별이다. 격자에 공은 정확히 한 개 존재하고, 별은 적어도 한 개 존재한다.

출력

모든 별을 얻을 수 있으면 YES, 아니면 NO를 출력한다.

예제 입력

3 7
#..O..#
#.###.#
*..#..*

예제 출력

NO

예제 입력 2

6 6
*..*##
..O...
*..*#.
####*.
......
.....#

예제 출력 2

YES

힌트