問題一覧 > 通常問題

No.2096 Rage With Our Friends

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

問題文

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

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

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

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

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

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

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

入力

$H$ $W$
$s_x$ $s_y$ $g_x$ $g_y$
$S_1$
$S_2$
$\vdots$
$S_H$

  • $H, W, s_x, g_x, s_y, g_y$ は整数である.
  • $2 \leq H, W \leq 2000$
  • $s_x = 1$
  • $g_x = H$
  • $1 \leq s_y, g_y \leq W$
  • $S_i (1 \leq i \leq H)$ は # および . からなる長さ $W$ の文字列である.
  • $S_{1,j} = $ . $(1 \leq j \leq W)$
  • $S_{g_x, g_y} =$ .

出力

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

サンプル

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

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

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

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

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

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

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