No.2096 Rage With Our Friends
タグ : / 解いたユーザー数 25
作問者 : 👑
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)$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。