No.2238 Rock and Hole
kumakuma
nok0
shino16Problem Statement
There is a grid with $H$ rows and $W$ columns, containing cells with rocks placed on them and cells with holes. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i,j)$.
When a rock is pushed, it keeps rolling in one direction, and when it reaches a cell with a hole, it falls into the hole. Each hole can hold only one rock.
Each rock can be pushed only once, and the next rock cannot be pushed until the pushed rock has entered a hole. Determine whether all the rocks can be dropped into holes by pushing the rocks in an appropriate order, each in one of the directions up, down, left, or right.
In addition, the path along which a rock rolls must not contain any of the following cells.
- A cell where another rock is present
- A cell with a hole that already contains a rock
r; if there is a hole in cell $(i,j)$, $S$$i,j$ is h; and if there is nothing, it is ..
Input
$H\ W$ $S$$1,1$ $S$$1,2$ $\ldots$ $S$$1,W$ $S$$2,1$ $S$$2,2$ $\ldots$ $S$$2,W$ $\vdots$ $S$$H,1$ $S$$N,2$ $\dots$ $S$$H,W$
- $1 \le H,W \le 10^5$
- $H\times W \le 10^5$
- $S$$i,j$ is one of
r,h, or. - All numbers in the input are integers
Output
On $1$ line, output Yes if all the rocks can be dropped into holes, and No otherwise.
Print a newline at the end.
Sample
Sample 1
Input
3 4 r... r.h. h...
Output
Yes
As shown in the image above, in Sample 1, all the rocks can be dropped into holes by first pushing the rock at (2,1) to the right into the hole at (2,3), and then pushing the rock at (1,1) downward into the hole at (3,1).
Sample 2
Input
4 4 r... r... h... h...
Output
No
Note that a rock cannot pass over a cell with a hole that already contains a rock.
Sample 3
Input
3 3 h.. ... ...
Output
Yes
Note that there may be no rocks at all.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。