No.2238 Rock and Hole
タグ : / 解いたユーザー数 40
作問者 :
kumakuma
/ テスター :
nok0
shino16
問題文
縦 $H$ マス、横 $W$ マスに広がるマス目があり、石の置かれたマスと穴が空いたマスが存在します。上から $i$ 番目で左から $j$ 番目のマスを $(i,j)$ と表します。
石を押すと一つの方向に転がり続け、穴の空いているマスに到着すると穴に落ちます。一つの穴には一つの石しか入りません。
各石は一度しか押すことが出来ず、押した石が穴に入るまで次の石を押すことは出来ません。適切な順番に石を上、下、左、右のいずれかの方向に押すことですべての石を穴に落とすことができるか判定してください。
また石の転がる経路には以下のマスが含まれてはいけません。
- 他の石が存在するマス
- すでに石が入っている穴が存在するマス
r 、マス $(i,j)$ に穴が存在する場合 $S$$i,j$ は h 、なにもない場合は.となります。
入力
$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$ は
r、h、.のいずれかである - 入力される数はすべて整数である
出力
$1$ 行に、すべての石を穴に落とすことができる場合はYes、できない場合はNoを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 4 r... r.h. h...
出力
Yes
上の画像の用にサンプル1では最初に(2,1)の石を右に動かし(2,3)の穴に落とし、次に(1,1)の石を下に押し(3,1)の穴に落とすことですべての石を穴に落とすことが出来ます。
サンプル2
入力
4 4 r... r... h... h...
出力
No
すでに石が入っている穴が存在するマスの上を石が通れないことに注意してください。
サンプル3
入力
3 3 h.. ... ...
出力
Yes
石がない場合もありえるので注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。