405752: GYM102059 B Dev, Please Add This!

Jaemin developed a puzzle game app.

A ball is placed on a cell in a grid. You can roll the ball upwards, downwards, to the left, or to the right. The ball rolls in that direction until it hits a wall or the boundary. Some cells have stars on them, and the player obtains the star when the ball stops there or passes through it. The objective of the game is to obtain all stars in the grid.

This app has a level editor where players can make and share their own levels. One day, someone suggested: “Please add a feature to check if my level is possible to solve!” Easier said than done, right?

The first line of the input consists of two integers, H (height) and W (width). (1 ≤ H, W ≤ 50) Each of the next H lines contains a string of legnth W which describes each row of the grid. “#” means a wall, “.” means a blank space, “O” means a ball, and “*” means a star. There is exactly one ball and at least one star on the grid.

Print “YES” if it is possible to obtain all stars, otherwise “NO”.

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

NO

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

YES