問題一覧 > 通常問題

No.2096 Rage With Our Friends

レベル : / AI推定難易度 : 2050 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 25
作問者 : 👑 AngrySadEight / テスター : chineristAC
お気に入りにしたユーザー ProblemId : 8442 / 自分の提出
問題文最終更新日: 2022-10-07 09:33:41
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 363 (順位表) の他の問題:

Problem Statement

A boy is traveling on a map with 2D coordinates. The map is given as strings $S$ with $H$ rows and $W$ columns. If $S_{i,j}$ is ., there is a foothold at coordinates $(i,j)$; if it is #, there is no foothold at coordinates $(i,j)$. For all $\boldsymbol{1 \leq j \leq W}$, $\boldsymbol{S_{1,j}=}$ . holds.

Initially, the boy is at coordinates $(s_x, s_y)$. His objective is to reach the goal at coordinates $(g_x, g_y)$. Here, $\boldsymbol{s_x = 1, g_x = H}$.

The boy has energy $E$, which is initially $E=0$. He can move using the following $2$ types of moves.

  • Normal jump: Let $(x, y)$ be his current coordinates. Choose one $x'$ satisfying $x' \leq x + 1 + \lfloor \frac{E}{2} \rfloor$ and move to $(x', y - 1)$ or $(x',y + 1)$. After that, his energy changes to $E=\max(0, x-x')$. This move can be performed only if there is a foothold at the destination coordinates.
  • Boost jump: Let $(x, y)$ be his current coordinates. Choose one $x'$ satisfying $x' \leq x + 1 + E$ and move to $(x',y - 1)$ or $(x',y + 1)$. After that, his energy changes to $E=\max(0, x-x')$. This move can be performed only if there is a foothold at the destination coordinates.

However, he cannot move to coordinates $(i, j)$ that do not satisfy $1 \leq i \leq H, 1 \leq j \leq W$.

Boost jumps are difficult and tiring, so he wants to perform as few of them as possible.

Find the minimum number of boost jumps required for the boy to reach the goal.

Input

$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$ are integers.
  • $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)$ is a string of length $W$ consisting of # and ..
  • $S_{1,j} = $ . $(1 \leq j \leq W)$
  • $S_{g_x, g_y} =$ .

Output

If the boy can reach the goal, print the minimum number of boost jumps required. If he cannot reach it, print -1.

Sample

Sample 1
Input
4 6
1 1 4 6
......
#.####
##.###
###.#.
Output
1

He can reach the goal with $1$ boost jump as follows.

  • From $(1,1)$, use a normal jump to move to $(2,2)$. $E=0$.
  • From $(2,2)$, use a normal jump to move to $(3,3)$. $E=0$.
  • From $(3,3)$, use a normal jump to move to $(4,4)$. $E=0$.
  • From $(4,4)$, use a normal jump to move to $(1,5)$. $E=3$.
  • From $(1,5)$, use a boost jump to move to $(4,6)$.
He cannot reach the goal with fewer boost jumps, so this is the minimum.

Sample 2
Input
3 3
1 2 3 2
...
###
...
Output
-1

There is no way to reach the goal.

Sample 3
Input
5 2
1 1 5 1
..
.#
.#
.#
.#
Output
3

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