0997 - 魔女っ娘ヒナくるん -Magic.09

時間制限 1 秒 / メモリ制限 256 MB / 得点 30 / Writer Doll / x 6 / 統計 /

TLE
1sec
MLE
256MB
得点
30

Magic.09 『Water Bridge』

前回のあらすじ

苦しい戦いの末、ヤヌメに勝利したヒナくるん。

しかし、体力はかなり奪われてしまった。

地下のより奥へ歩いて向かうヒナくるんとアヤの目の前に、

大きな橋が現れたのだった・・・

本編

ヒナくるん

「見てアヤ、あの橋、立て札があるわ。」

アヤ

「どれどれ、『このはしわたるべからず』・・・。真ん中を歩きましょう。」

ヒナくるん

「ダメよアヤ！！渡っちゃダメって書いてあるもの！！

　きっと親切な人が教えてくれたのよ！！下の川を渡るしかないわ！！」

アヤ

「本当にそうならいいけど。まあ川も見たところ浅そうだし、そうしましょうか。」

川を渡っていると、突如ヒナくるんの真下の水が高く高く吹き上がり、ヒナくるんは水の中に囚われてしまった！！

ヒナくるん

「ボボボボボボボボ!!!!ゴボボボッボッボボッ!!!!ボボボッ!!!!!」

アヤ

「やっぱり罠じゃん・・・今助けるから取り敢えず落ち着きなさい！！」

問題

水の中に、ヒナくるんが囚われている。助けに、行こう。

あっ、この水、重い！！！

アヤは起こした風の風圧によって、ヒナくるんを水牢から吹き飛ばそうとしている。

川はH*Wの方眼状になっており、各地点において異なる水牢が息を潜めている。

ヒナくるんは水牢から吹き飛ばされると、その座標から上下左右Mマスのいずれかに到着し、

そこでまた同じように水牢に幽閉される。かわいそうに。

なお、その際にアヤは魔力をC消費する。

MとCは各地点において異なる。

ヒナくるんが幽閉されている初期位置と、各地点に置けるMとCの値が与えられるので、

ヒナくるんがある地点に辿り着くまでにアヤが消費する魔力の値の最小を全ての地点において出力せよ。

入出力形式

入力形式

一行目に、川の縦と横の幅 H,W が空白区切りで与えられる。

二行目に、ヒナくるんが幽閉されている初期位置 SH,SW が空白区切りで与えられる。

次にH行にかけて、各水牢においてヒナくるんが吹き飛ばされるマス数 Mi,j が空白区切りで与えられる。

次にH行にかけて、各水牢においてアヤが消費するコスト Ci,j が空白区切りで与えられる。

H W
SH SW
M1,1 M1,2 .. M1,W
M2,1 M2,2 .. M2,W
..
MH,1 MH,2 .. MH,W
C1,1 C1,2 .. C1,W
C2,1 C2,2 .. C2,W
..
CH,1 CH,2 .. CH,W

出力形式

H行にかけて、ヒナくるんの初期位置からそのマスに辿り着くまでに

アヤが消費する魔力の最小値 Ti,jを空白区切りで出力せよ。

どうしてもそのマスに辿り着けない場合は、Tの代わりに"X"(アルファベット大文字エックス）を出力せよ。

T1,1 T1,2 .. T1,W
T2,1 T2,2 .. T2,W
..
TH,1 TH,2 .. TH,W

制約

  • 1 ≦ H,W ≦ 1000
  • 1 ≦ Mi,j ≦ 1000 (1≦i≦H , 1≦j≦W)
  • 1 ≦ SH ≦ H
  • 1 ≦ SW ≦ W
  • 1 ≦ C ≦ 100
  • ヒナくるんが川の範囲内から離れてしまうような吹き飛ばしは行われないものとする。

入出力例

入力例

5 5
1 1
3 2 1 4 1
1 2 3 4 5
2 1 4 2 1
3 1 2 2 1
1 3 2 2 1
1 2 3 4 5
2 3 4 5 1
2 3 5 1 2
4 5 1 2 3
5 4 3 2 1

出力例

0 X X 1 X
X 11 13 7 17
11 8 11 7 15
1 7 12 5 12
13 7 17 5 11