D - アイスリンクの脱出 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は、縦 H マス、横 W マスの長方形のアイスリンクに閉じ込められてしまいました。リンク内には N 個の柱が立っています。 i 番目の柱は座標 (R_i, C_i) にあります。ここで、座標 (r, c) は上から r 行目、左から c 列目のマスを表します。

高橋君は現在、リンクの左上隅の座標 (1, 1) におり、右下隅の座標 (H, W) にあるゴールを目指しています。

アイスリンクの氷は非常に滑りやすく、一度滑り出すと途中で方向を変えたり止まったりすることができません。高橋君は1回の移動で、上・下・左・右の4方向のうちいずれか1つを選んで滑り始め、以下のいずれかの条件を満たすまでその方向に直進し続けます：

  • リンクの端に到達する： リンクの外に出ることはできないため、端のマスで停止します。
  • 柱の手前に到達する： 滑っている方向の次のマスに柱がある場合、柱のあるマスには入れないため、その手前のマスで停止します。

ここで、上方向とは行番号が減る方向、下方向とは行番号が増える方向、左方向とは列番号が減る方向、右方向とは列番号が増える方向を指します。

選んだ方向に1マスも進めない場合（すなわち、隣のマスが柱であるか、既にリンクの端にいてその方向にはマスが存在しない場合）は、高橋君は移動せず元のマスに留まります。この場合も1回の移動として数えます。

高橋君は同じマスを何度でも訪れることができます。

高橋君が座標 (1, 1) から出発し、座標 (H, W) で停止するために必要な最小の移動回数を求めてください。座標 (H, W) で停止するとは、上記の移動ルールに従って滑った結果、座標 (H, W) で止まることを意味します。滑っている途中に座標 (H, W) を通過しただけでは、ゴールに到達したとはみなしません。

到達が不可能な場合は -1 を出力してください。

なお、座標 (1, 1) および座標 (H, W) には柱は立っていないことが保証されます。

制約

  • 2 \leq H \leq 100
  • 2 \leq W \leq 100
  • 0 \leq N \leq H \times W - 2
  • 1 \leq R_i \leq H
  • 1 \leq C_i \leq W
  • (R_i, C_i) \neq (1, 1)
  • (R_i, C_i) \neq (H, W)
  • i \neq j ならば (R_i, C_i) \neq (R_j, C_j)
  • 入力はすべて整数

入力

H W N
R_1 C_1
R_2 C_2
\vdots
R_N C_N
  • 1 行目には、アイスリンクの縦のマス数を表す H 、横のマス数を表す W 、柱の個数を表す N が、スペース区切りで与えられる。
  • 続く N 行には、各柱の座標が与えられる。 N = 0 の場合、この部分は存在しない。
  • 1 + i 行目（1 \leq i \leq N）では、 i 番目の柱の行番号 R_i と列番号 C_i が、スペース区切りで与えられる。

出力

高橋君が座標 (1, 1) から座標 (H, W) で停止するために必要な最小の移動回数を 1 行で出力せよ。到達が不可能な場合は -1 を出力せよ。

入力例 1

3 3 1
2 2

出力例 1

2

入力例 2

5 6 3
2 3
4 4
3 6

出力例 2

2

入力例 3

10 10 8
1 5
3 1
3 10
5 5
7 3
7 8
10 4
2 8

出力例 3

4

Score : 400 pts

Problem Statement

Takahashi is trapped in a rectangular ice rink with H rows and W columns. There are N pillars standing inside the rink. The i-th pillar is located at coordinates (R_i, C_i). Here, coordinates (r, c) denote the cell in the r-th row from the top and the c-th column from the left.

Takahashi is currently at the top-left corner at coordinates (1, 1) and aims to reach the goal at the bottom-right corner at coordinates (H, W).

The ice on the rink is extremely slippery, and once he starts sliding, he cannot change direction or stop midway. In one move, Takahashi chooses one of the four directions — up, down, left, or right — and begins sliding, continuing straight in that direction until one of the following conditions is met:

  • Reaching the edge of the rink: Since he cannot go outside the rink, he stops at the edge cell.
  • Reaching the cell just before a pillar: If the next cell in the sliding direction contains a pillar, he cannot enter the cell with the pillar, so he stops at the cell just before it.

Here, up means the direction of decreasing row number, down means increasing row number, left means decreasing column number, and right means increasing column number.

If he cannot advance even one cell in the chosen direction (i.e., the adjacent cell contains a pillar, or he is already at the edge of the rink and no cell exists in that direction), Takahashi does not move and stays at his current cell. This still counts as one move.

Takahashi may visit the same cell any number of times.

Find the minimum number of moves required for Takahashi to start from coordinates (1, 1) and stop at coordinates (H, W). Stopping at coordinates (H, W) means that, following the movement rules described above, he comes to a stop at coordinates (H, W). Simply passing through coordinates (H, W) while sliding does not count as reaching the goal.

If it is impossible to reach the goal, output -1.

It is guaranteed that there are no pillars at coordinates (1, 1) or coordinates (H, W).

Constraints

  • 2 \leq H \leq 100
  • 2 \leq W \leq 100
  • 0 \leq N \leq H \times W - 2
  • 1 \leq R_i \leq H
  • 1 \leq C_i \leq W
  • (R_i, C_i) \neq (1, 1)
  • (R_i, C_i) \neq (H, W)
  • If i \neq j, then (R_i, C_i) \neq (R_j, C_j)
  • All input values are integers

Input

H W N
R_1 C_1
R_2 C_2
\vdots
R_N C_N
  • The first line contains H, the number of rows of the ice rink, W, the number of columns, and N, the number of pillars, separated by spaces.
  • The following N lines contain the coordinates of each pillar. If N = 0, this part does not exist.
  • The (1 + i)-th line (1 \leq i \leq N) contains the row number R_i and column number C_i of the i-th pillar, separated by spaces.

Output

Print in one line the minimum number of moves required for Takahashi to stop at coordinates (H, W) starting from coordinates (1, 1). If it is impossible, print -1.

Sample Input 1

3 3 1
2 2

Sample Output 1

2

Sample Input 2

5 6 3
2 3
4 4
3 6

Sample Output 2

2

Sample Input 3

10 10 8
1 5
3 1
3 10
5 5
7 3
7 8
10 4
2 8

Sample Output 3

4