問題一覧 > 通常問題

No.1638 Robot Maze

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 149
作問者 : harurunharurun / テスター : magstamagsta saksak
3 ProblemId : 6680 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-09 15:15:33

問題文

縦 $H$ 行、横 $W$ 列のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。

各マス $(i,j)$ $(1≤i≤H,1≤j≤W)$ についての情報が $C_{i,j}$ で与えられます。

$C_{i,j}$ が.ならばマス $(i,j)$ は空マスであり、 $C_{i,j}$ が #ならばマス $(i,j)$ は固い壁マスであり、$C_{i,j}$ が @ならばマス $(i,j)$ は脆い壁マスです。

ロボットのT君は上下左右に隣り合うマスへの移動を繰り返し、マス $(x_s,y_s)$ から出発しマス $(x_t,y_t)$ に辿り着こうとしています。

T君は出発前に、ある非負整数 $x$ を選んでコスト $P\times x$ で脆い壁を $x$ 個破壊し、空マスにすることができます。

出発後T君がマス $(i,j)$ にいるとき、以下の移動ができます。

  • マス $(i-1,j)$ が空マスであるならば、マス $(i-1,j)$ にコスト $U$ で移動できる。

  • マス $(i+1,j)$ が空マスであるならば、マス $(i+1,j)$ にコスト $D$ で移動できる。

  • マス $(i,j+1)$ が空マスであるならば、マス $(i,j+1)$ にコスト $R$ で移動できる。

  • マス $(i,j-1)$ が空マスであるならば、マス $(i,j-1)$ にコスト $L$ で移動できる。

T君がマス $(x_t,y_t)$ にコスト $K$ 以下で辿り着くことは可能でしょうか?

可能ならばYes、不可能ならばNoと出力してください。

制約

  • $2≤H,W≤100$

  • $0≤U,D,R,L≤100$

  • $0≤K≤10^{13}$

  • $0≤P≤10^{9}$

  • $C_{i,j}$ は.または#または@である。

  • $1≤x_s,x_t≤H$

  • $1≤y_s,y_t≤W$

  • $(x_s,y_s)\neq (x_t,y_t)$

  • $(x_s,y_s)$,$(x_t,y_t)$ は空マスである。

入力

$H\ W$
$U\ D\ R\ L\ K\ P$
$x_s\ y_s\ x_t\ y_t$
$C_{1,1}...C_{1,W}$
$\vdots$
$C_{H,1}...C_{H,W}$
  • $1$ 行目には $H,W$ が空白区切りで与えれる。

  • $2$ 行目には $U,D,R,L,K,P$ が空白区切りで与えれる。

  • $3$ 行目には $x_s,y_s,x_t,y_t$ が空白区切りで与えられる。

  • $4$ 行目から $H+3$ 行目には $C_{i,1}...C_{i,W}$ が与えれる。$(1≤i≤H)$

出力

答えを $1$ 行に出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3 3
1 1 1 1 8 16
1 1 3 1 
..@
##@
..@
出力
No

コスト $54$ かかるので No を出力してください。

サンプル2
入力
2 2
0 0 0 0 1 1
1 1 2 2
.@
#.
出力
Yes

コスト $1$ で辿り着けます。

サンプル3
入力
2 2
100 100 100 100 100 104060401
1 1 2 2
.#
#.
出力
No

辿り着けない場合もNoと出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。