問題一覧 > 通常問題

No.2096 Rage With Our Friends

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : 👑 AngrySadEightAngrySadEight / テスター : chineristACchineristAC
1 ProblemId : 8442 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-07 09:33:41

問題文

一人の少年が,2次元座標状のマップ上を旅しています.マップは HHWW 列の文字列 SS で与えられ,Si,jS_{i,j}. であれば座標 (i,j)(i,j) に足場があることを, # であれば座標 (i,j)(i,j) に足場がないことを表します.すべての 1jW\boldsymbol{1 \leq j \leq W} に対し,S1,j=\boldsymbol{S_{1,j}=} . です.

最初,少年は座標 (sx,sy)(s_x, s_y) にいます.少年の目標は,ゴールである座標 (gx,gy)(g_x, g_y) に行くことです.ここで,sx=1,gx=H\boldsymbol{s_x = 1, g_x = H} です.

少年は,エネルギー EE を持っており,はじめ E=0E=0 です.少年は,次のような 22 種類の移動方法を用いることで,移動することができます.

  • 通常ジャンプ:今いる座標を (x,y)(x, y) とする.xx+1+E2x' \leq x + 1 + \lfloor \frac{E}{2} \rfloor を満たすような xx' をひとつ選び, (x,y1)(x', y - 1) または (x,y+1)(x',y + 1) に移動する.その後,少年の持つエネルギーは, E=max(0,xx)E=\max(0, x-x') に変化する.この移動は,移動先の座標に足場がある場合に限り行える.
  • ブーストジャンプ:今いる座標を (x,y)(x, y) とする.xx+1+Ex' \leq x + 1 + E を満たすような xx' をひとつ選び, (x,y1)(x',y - 1) または (x,y+1)(x',y + 1) に移動する.その後,少年の持つエネルギーは, E=max(0,xx)E=\max(0, x-x') に変化する.この移動は,移動先の座標に足場がある場合に限り行える.

ただし,1iH,1jW1 \leq i \leq H, 1 \leq j \leq W を満たさないような座標 (i,j)(i, j) への移動を行うことはできません.

ブーストジャンプは難しい上に疲れるので,出来るだけその回数を少なくしたいと思っています.

少年がゴールに到達するのに必要なブーストジャンプの回数の最小値を求めてください.

入力

HH WW
sxs_x sys_y gxg_x gyg_y
S1S_1
S2S_2
\vdots
SHS_H

  • H,W,sx,gx,sy,gyH, W, s_x, g_x, s_y, g_y は整数である.
  • 2H,W20002 \leq H, W \leq 2000
  • sx=1s_x = 1
  • gx=Hg_x = H
  • 1sy,gyW1 \leq s_y, g_y \leq W
  • Si(1iH)S_i (1 \leq i \leq H)# および . からなる長さ WW の文字列である.
  • S1,j=S_{1,j} = . (1jW)(1 \leq j \leq W)
  • Sgx,gy=S_{g_x, g_y} = .

出力

少年がゴールにたどり着ける場合,必要な最小のブーストジャンプの回数を出力せよ.たどり着けない場合は -1 を出力せよ.

サンプル

サンプル1
入力
4 6
1 1 4 6
......
#.####
##.###
###.#.
出力
1

次のようにすることで,ブーストジャンプ 11 回でゴールにたどり着けます.

  • (1,1)(1,1) から,通常ジャンプを使用して (2,2)(2,2) に移動する.E=0E=0 である.
  • (2,2)(2,2) から,通常ジャンプを使用して (3,3)(3,3) に移動する.E=0E=0 である.
  • (3,3)(3,3) から,通常ジャンプを使用して (4,4)(4,4) に移動する.E=0E=0 である.
  • (4,4)(4,4) から,通常ジャンプを使用して (1,5)(1,5) に移動する.E=3E=3 である.
  • (1,5)(1,5) から,ブーストジャンプを使用して (4,6)(4,6) に移動する.
それより少ない回数のブーストジャンプではゴールにたどり着くことはできないため,これが最小となります.

サンプル2
入力
3 3
1 2 3 2
...
###
...
出力
-1

どうやってもゴールにたどり着くことはできません.

サンプル3
入力
5 2
1 1 5 1
..
.#
.#
.#
.#
出力
3

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