No.323 yuki国

レベル : / 実行時間制限 : 1ケース 5秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 58
作問者 : ぴろず

4 ProblemId : 845

Note

この問題はAdvent Calendar Contest Advent Calendar 2015の16日目の問題として作られました。

WriterはJavaとPyPy2で余裕を持ってACできることを確認しましたが、Python2ではTLEしました。
比較的低速な言語を使用している方は実行時間に注意してください。

問題文

太郎君は長方形の空き地で雪だるまを作っていて、今は雪球を転がしているところです。

空き地を$H$行,$W$列のマス目で表します。第$i(0 \leq i \leq H-1)$行、第$j(0 \leq j \leq W-1)$列のマスをマス$(i,j)$と呼びます。

はじめ、雪球はマス$(S_i,S_j)$にあり、その大きさは$A$です。
太郎君は雪球を上下左右いずれかの隣接したマスに移動させることができます。ただし空き地の外に出てはいけません。
このとき、移動先のマスに雪が積もっていれば雪球の大きさは$1$増え、そうでなければ雪球の大きさは$1$減ります。
雪球の大きさが$0$以下になると、雪球は溶けてしまいます。つまり、雪球の大きさは常に$1$以上でなければなりません。

太郎君が雪球の大きさをちょうど$B$にしてマス$(G_i,G_j)$に運ぶことが可能か判定してください。

入力

$H$ $W$
$A$ $S_i$ $S_j$
$B$ $G_i$ $G_j$
$M_0$
$M_1$
$\vdots$
$M_{H-1}$

$1$行目に2つの整数$H$,$W$が空白区切りで与えられます。
$2$行目に3つの整数$A$,$S_i$,$S_j$が空白区切りで与えられます。
$3$行目に3つの整数$B$,$G_i$,$G_j$が空白区切りで与えられます。
$4$行目からの$H$行に、長さ$W$の文字列$M_0 \dots M_{H-1}$が与えられます。
$M_i$の$j(0 \leq j \leq W-1)$列目が'*'(アスタリスク)の時、マス$(i,j)$には雪が積もっています。 '.'(ピリオド)の時、マス$(i,j)$には雪が積もっていません。

$1 \leq H,W \leq 50$
$1 \leq A,B \leq 1000$
$0 \leq S_i,G_i \leq H-1$
$0 \leq S_j,G_j \leq W-1$
$(A,S_i,S_j) \neq (B,G_i,G_j)$
$M_i(0 \leq i \leq H-1)$は'*'(アスタリスク)と'.'(ピリオド)のみからなる長さ$W$の文字列である。

出力

太郎君が雪球の大きさをちょうど$B$にしてマス$(G_i,G_j)$に運ぶことが可能ならば'Yes'を、不可能ならば'No'を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
2 4
2 0 0
2 1 3
*.*.
.*.*
出力
Yes

例えば、右・右・右・下と移動することで目標のマスにつき、雪球の大きさは2となります。
雪球の大きさは$2$→$1$→$2$→$1$→$2$と変化します。

サンプル2
入力
2 1
1 0 0
4 1 0
*
*
出力
Yes

下・上・下と$3$回移動することで目標のマスにつき、雪球の大きさは4となります。
はじめに下に移動した後に目標のマスについていますが、この時点では雪球の大きさが足りていません。

サンプル3
入力
4 4
3 3 0
8 0 3
.***
..**
...*
....
出力
No

雪球の大きさが途中で0以下になってはいけないので、目標のマスに辿りつけません。

サンプル4
入力
8 10
1 1 4
5 1 4
....*.*.*.
.........*
..........
.*.*.*...*
*...**....
.........*
*.........
.*.*.*.*.*
出力
Yes

最初に雪球があるマスと目標のマスは同じなことがあります。

サンプル5
入力
1 10
1 0 0
6 0 9
**......**
出力
Yes

サンプル6
入力
4 5
5 1 1
6 1 3
.*..*
*....
*...*
****.
出力
No

提出ページヘ