Problem:


現代的な屋敷(Modern Mansion)

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

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

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

課題

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

制限

2 ≤ M ≤ 100 000      屋敷の東西方向の部屋の個数

2 ≤ N ≤ 100 000     屋敷の南北方向の部屋の個数

1 ≤ K ≤ 200 000     スイッチのある部屋の個数

1 ≤ Xi ≤ M     スイッチのある部屋の東西方向の位置

1 ≤ Yi ≤ N     スイッチのある部屋の南北方向の位置

入力

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

 1 行目には，整数 M, N, K が空白を区切りとして書かれている．M は屋敷の東西方向の部屋の個数，N は屋敷の南北方向の部屋の個数，K はスイッチのある部屋の個数を表す．

 続く K 行のうちの i 行目(1 ≤ i ≤ K) には，整数 Xi, Yi が空白を区切りとして書かれている．これは，部屋(Xi, Yi) の中央にスイッチがあることを表す．K 個の組(X1, Y1), (X2, Y2),..., (XK, YK) は互いに異なる．

出力

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

採点基準

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

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

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

入出力例

入力例 1

3 2 1
1 2

 出力例 1

4

この例では，以下の行動によって 4 分間で部屋(1, 1) の中央から部屋(3, 2) の中央へ移動することができ，これが最短である．

 部屋(1, 2) の中央へ移動する．

 部屋(1, 2) の中央のスイッチを押す．

 部屋(2, 2) の中央へ移動する．

 部屋(3, 2) の中央へ移動する．

このときの屋敷の様子が以下の図に表されている．図では右方向が東，上方向が北であり，×印はあなたの位置，○印はスイッチを表す．

入力例 2

3 2 1
2 1

出力例 2

-1

この例では，あなたは部屋(3, 2) に辿り着くことができない．

入力例 3

8 9 15
3 1
3 2
3 7
3 8
1 1
4 5
4 3
5 6
5 8
6 3
6 2
7 5
8 9
8 6
8 5

出力例 3

25

この例では，最初の屋敷の様子は以下の図のようになっている．部屋(1, 1) や部屋(M, N) の中央にスイッチがある可能性もあることに注意せよ．

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
3 2 1
1 2


Sample output:
4

Submission status: Accepted

Solution code:
#!/bin/env python
import sys
import heapq
from collections import defaultdict, deque


class Grid:
    '''
    Grid provide 2 dim axis search for grid.
    '''
    def __init__(self, points):
        self.by_d = {0: defaultdict(list), 1: defaultdict(list)}
        for x, y in points:
            self.by_d[0][x].append((x, y))
            self.by_d[1][y].append((x, y))

    def get_points(self, axis, line_no):
        return self.by_d[axis][line_no]

    def remove(self, point):
        self.by_d[0][point[0]].remove(point)
        self.by_d[1][point[1]].remove(point)

    def get_lines(self, direction):
        return self.by_d[direction].keys()


class ModernMansion(Grid):
    def __init__(self, switches, goal):
        super().__init__(switches)
        self.goal = goal

    def remove_orphan(self):
        '''
        Removes switch recursivery, that only one switch exists in line.
        But leaves switch in line on START.
        '''
        q = deque()
        for direction in (0, 1):
            for line in self.get_lines(direction):
                q.append((direction, line))
        while q:
            direction, line = q.pop()
            switches = self.get_points(direction, line)
            if len(switches) != 1:
                continue
            sw = switches[0]
            # But reaves switch in line on START.
            if sw[0] == 1 or sw == self.goal:
                continue
            self.remove(sw)
            next_dir = (direction + 1) % 2
            q.append((next_dir, sw[next_dir]))

    def has_route(self):
        '''
        If no switches exists in goal line, it never can goal.
        '''
        return len(self.by_d[0][self.goal[0]]) > 1 \
            or len(self.by_d[1][self.goal[1]]) > 1

    def get_sameline_switch(self, direction, sw):
        return (s for s in self.get_points(direction, sw[direction])
                if s != sw)


class Searcher:
    def __init__(self, grid):
        self.grid = grid
        self.q = []
        self.best_time = {}
        self.deadline = {0: set(), 1: set()}

    def next_depth(self, t, current, direction):
        # ゴールであれば、ゴールの時間を返し終了
        if current == self.grid.goal:
            return t - 1  # remove last switch push time.

        # 該当行が、既に全探索済みであれば、打ち切り
        if current[direction] in self.deadline[direction]:
            return

        next_dir = (direction + 1) % 2

        has_next_switch = False
        for sw in self.grid.get_sameline_switch(direction, current):
            # sw での時間は、現在の時間(t) + 距離 + スイッチ押下(1)
            next_t = t + abs(sw[next_dir] - current[next_dir]) + 1
            best_t = self.best_time.get(sw, float('inf'))
            if best_t <= next_t:
                continue
            # swへの最短経路を発見
            self.best_time[sw] = next_t
            heapq.heappush(self.q, (next_t, sw, next_dir))
            has_next_switch = True

        # 1つもbest time となるスイッチがなければ、その行自体NG
        if not has_next_switch:
            self.deadline[direction].add(current[direction])

    def search(self):
        ''' Returns all "time" '''
        # 最初に、duration:0 方向にしか移動できないというルールを、
        # (1, 0)から始めることで実現
        self.q.append((0, (1, 0), 0))
        while self.q:
            res = self.next_depth(*heapq.heappop(self.q))
            if res:
                yield res - 1  # remove first move (1, 0) to (1, 1)

    def search_one(self):
        ''' returns best or -1 '''
        try:
            return next(self.search())
        except StopIteration:
            return -1


if __name__ == '__main__':
    M, N, K = map(int, input().split())
    switches = [tuple(map(int, input().split())) for _ in range(K)]
    switches.append((M, N))

    grid = ModernMansion(switches, (M, N))
    grid.remove_orphan()
    if not grid.has_route():
        print('-1')
        sys.exit()

    searcher = Searcher(grid)
    res = searcher.search_one()
    print(res)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
M, N, K = map(int, input().split())

X = [[] for i in range(M)]
Y = [[] for i in range(N)]

for i in range(K):
    x, y = map(int, input().split()); x -= 1; y -= 1
    X[x].append((y, i))
    Y[y].append((x, i))

G0 = [[] for i in range(K)]
G1 = [[] for i in range(K)]
for x in range(M):
    vs = X[x]
    if vs:
        vs.sort()
        prv = vs[0]
        for v in vs[1:]:
            d = v[0] - prv[0]
            G0[prv[1]].append((v[1], d))
            G0[v[1]].append((prv[1], d))
            prv = v
for y in range(N):
    vs = Y[y]
    if vs:
        vs.sort()
        prv = vs[0]
        for v in vs[1:]:
            d = v[0] - prv[0]
            G1[prv[1]].append((v[1], d))
            G1[v[1]].append((prv[1], d))
            prv = v

INF = 10**18
que = []
D0 = [INF]*K; D1 = [INF]*K
if X[0]:
    y0, k = X[0][0]
    que.append((y0, 0, k))
while que:
    cost, t, v = heappop(que)
    if not t:
        if D0[v] < cost:
            continue
        for w, d in G0[v]:
            if cost + d < D0[w]:
                D0[w] = cost + d
                heappush(que, (cost + d, 0, w))
        if cost + 1 < D1[v]:
            D1[v] = cost + 1
            heappush(que, (cost + 1, 1, v))
    else:
        if D1[v] < cost:
            continue
        for w, d in G1[v]:
            if cost + d < D1[w]:
                D1[w] = cost + d
                heappush(que, (cost + d, 1, w))
        if cost + 1 < D0[v]:
            D0[v] = cost + 1
            heappush(que, (cost + 1, 0, v))
ans = INF
if X[M-1]:
    y0, k = X[M-1][-1]
    ans = min(ans, D0[k] + (N-1-y0))
if Y[N-1]:
    x0, k = Y[N-1][-1]
    ans = min(ans, D1[k] + (M-1-x0))
if ans < INF:
    print(ans)
else:
    print(-1)