407953: GYM102948 C White Fang

A group of men are traveling with supplies to Fort McGurry in the higher area of the Yukon Territory. After setting up camp for the night, they realize that they are surrounded by wolves. The travelers have a large number of tamed dogs, and they want to be alerted by any attempt by the wolf pack to attack.

The camp can be modeled as a rectangle consisting of $$$R \times C$$$ cells. Each cell is either empty, contains a person, a wolf, or a dog. People and dogs always stay in place, but wolves can roam freely around the camp, by repeatedly moving to the left, right, up or down to a neighboring cell. When a wolf enters a cell with a person, it attacks it. However, no wolf can enter a cell with a dog. Can you coordinate a placement of dogs in the camp in such a way that no wolf can reach any traveler? Note that a dog cannot be placed in a cell that a wolf starts in, and the number of dogs available can be assumed to be at least $$$R \times C$$$. No wolf can move outside the designated rectangle of cells.

The first line of input contains two integers, $$$R$$$ and $$$C$$$ ($$$1 \leq R, C \leq 50$$$), denoting the number of rows and the numbers of columns respectively.

Each of the following $$$R$$$ lines is a string consisting of exactly $$$C$$$ characters, representing one row of the camp. In this context, 'P' means a person, 'W' a wolf and '.' an empty cell.

Output a single line with the word "No" if a wolf can reach a person without traversing a cell with a dog in it for any setup, and "Yes" otherwise.

6 6
..P...
..P.W.
.P....
..W...
...W..
......

Yes

1 2
PW

No