現代的な屋敷 (Modern Mansion)

あなたは，ある大きな屋敷に迷い込んでしまった．この屋敷は正方形の部屋が東西南北に格子状に，東西方向に \(M\) 列，南北方向に \(N\) 行の合計 \(M \times N\) 個並んだ構造をしている．西から \(x\) 列目 (\(1 \leqq x \leqq M\))，南から \(y\) 行目 (\(1 \leqq y \leqq N\)) にある部屋を \((x, y)\) で表す．

東西南北に隣り合う \(2\) 部屋の間は，壁の中央にある扉により結ばれている．それぞれの扉は，閉じていて通行不可能な状態か，開いていて通行可能な状態のいずれかにある．扉が開いているとき，それらの部屋の中央間を移動するのに \(1\) 分間かかる．また，いくつかの部屋の中央にはスイッチがあり，スイッチを \(1\) 分間押し続けると，屋敷内のすべての扉の開閉の状態が切り替わる．

今，東西に隣り合う \(2\) 部屋を結ぶすべての扉は閉じていて，南北に隣り合う \(2\) 部屋を結ぶすべての扉は開いている．あなたは今部屋 \((1, 1)\) の中央にいて，部屋 \((M, N)\) の中央まで最短時間で移動したい．

課題

屋敷の大きさ \(M, N\) および，スイッチのある \(K\) 個の部屋の位置 \((X_1, Y_1), (X_2, Y_2), \ldots, (X_K, Y_K)\) が与えられる．東西に隣り合う \(2\) 部屋を結ぶすべての扉は閉じていて，南北に隣り合う \(2\) 部屋を結ぶすべての扉は開いている状態から始めて，部屋 \((1, 1)\) の中央から部屋 \((M, N)\) の中央まで移動するのに最短で何分かかるかを求めるプログラムを作成せよ．ただし，部屋 \((M, N)\) に辿り着くことができないときはそれを指摘せよ．

標準入力から以下のデータを読み込め．

• \(1\) 行目には，整数 \(M, N, K\) が空白を区切りとして書かれている．\(M\) は屋敷の東西方向の部屋の個数，\(N\) は屋敷の南北方向の部屋の個数，\(K\) はスイッチのある部屋の個数を表す．
• 続く \(K\) 行のうちの \(i\) 行目 (\(1 \leqq i \leqq K\)) には，整数 \(X_i, Y_i\) が空白を区切りとして書かれている．これは，部屋 \((X_i, Y_i)\) の中央にスイッチがあることを表す．\(K\) 個の組 \((X_1, Y_1), (X_2, Y_2), \ldots, (X_K, Y_K)\) は互いに異なる．

標準出力に，移動に最短で何分かかるかを表す整数を \(1\) 行で出力せよ．ただし，部屋 \((M, N)\) に辿り着くことができないときは代わりに整数 \(-1\) を出力せよ．

採点用データのうち，配点の \(20\) %分については，\(M \leqq 1\,000\)，\(N \leqq 1\,000\) を満たす．

採点用データのうち，配点の \(30\) %分については，\(K \leqq 2\,000\) を満たす．

採点用データのうち，配点の \(50\) %分については，これら \(2\) つの条件の少なくとも一方を満たす．また，これら \(2\) つの条件の両方を満たすような採点用データはない．

JOI 2013 · JCIOI · CC BY-SA 4.0