問題一覧 > 通常問題

No.2695 Warp Zone

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 120
作問者 : tkmstkms / テスター : KowerKoint2010KowerKoint2010 timitimi hibit_athibit_at
1 ProblemId : 10615 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-22 21:32:10

問題文

$H$ 行 $W$ 列のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ とします。

tkms 君は、グリッドの $(1,1)$ から $(H,W)$ までなるべく早く移動したいです。

グリッド上には $N$ 個のワープがあり、$i(1 \leq i \leq N)$ 個目のワープは $(a_i,b_i)$ から $(c_i,d_i)$ につながっています。逆走はできません。

tkms 君は $1$ 回の動作で

  • 四方に $1$ マス移動する。つまり、$(x,y)$ にいるとき $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$ のいずれか $1$ つに移動する。
  • ワープを通る。

のいずれかが可能です。ワープの始点にいるとき、ワープを通らずに四方に移動しても構いません。

グリッドの外側に移動することはできません。

$(1,1)$ を出発して $(H,W)$ に到達するまでの動作の回数の最小値を求めてください。

入力

$H\ W\ N$
$a_1\ b_1\ c_1\ d_1$
$a_2\ b_2\ c_2\ d_2$
$⋮$
$a_N\ b_N\ c_N\ d_N$

  • 入力はすべて整数
  • $2 \leq H,W \leq 10^9$
  • $0 \leq N \leq \mathbb{min}(10^3,\frac{H \times W-2}{2})$
  • $1 \leq a_i,c_i \leq H (1 \leq i \leq N)$
  • $1 \leq b_i,d_i \leq W (1 \leq i \leq N)$
  • $(1,1),(H,W),(a_1,b_1),\dots,(a_N,b_N),(c_1,d_1), \dots,(c_N,d_N)$ はすべて異なる

出力

最小値を整数で出力してください。

サンプル

サンプル1
入力
3 3 1
1 2 3 2
出力
3

以下のようにすると、$3$ 回で $(1,1)$ から $(3,3)$ まで移動できます。

  • $(1,1)$ から $(1,2)$ に移動する。
  • ワープを通り、$(3,2)$ に移動する。
  • $(3,2)$ から $(3,3)$ に移動する。
サンプル2
入力
5 4 2
2 4 1 2
4 4 2 1
出力
7

ワープは逆走することができません。

サンプル3
入力
10 10 5
4 5 3 3
4 6 6 10
8 8 10 5
9 5 3 1
9 3 3 4
出力
13

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