結果

問題 No.157 2つの空洞
コンテスト
ユーザー はむ吉🐹
提出日時 2016-02-29 20:42:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 67 ms / 2,000 ms
コード長 2,818 bytes
コンパイル時間 334 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 72,804 KB
最終ジャッジ日時 2024-09-24 12:52:44
合計ジャッジ時間 2,301 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env pypy3
# -*- coding: utf-8 -*-

import array
import collections
import copy
import heapq
import itertools
import sys


DELTA = [(1, 0), (-1, 0), (0, 1), (0, -1)]
INF = 10 ** 4
IS_HOLLOW = True
IS_WALL = False


class RecursiveDepthFirstSearch(object):

    def __init__(self, width, height, stage):
        self.width = width
        self.height = height
        self.stage = stage
        self.hollow_representatives = []

    def search(self, r0, c0):
        if r0 < 0 or r0 >= self.height or c0 < 0 or c0 >= self.width:
            pass
        elif self.stage[r0][c0] == IS_WALL:
            pass
        else:
            self.stage[r0][c0] = IS_WALL
            for dr, dc in DELTA:
                self.search(r0 + dr, c0 + dc)

    def find_hollow_representatives(self):
        for r, c in itertools.product(range(self.height), range(self.width)):
            if self.stage[r][c] == IS_HOLLOW:
                self.hollow_representatives.append((r, c))
                self.search(r, c)
        return self.hollow_representatives


class Dijkstra(object):

    def __init__(self, width, height, stage, start, goal):
        self.width = width
        self.height = height
        self.stage = stage
        self.start = start
        self.goal = goal
        self.dist = None

    def init_dist(self):
        self.dist = collections.defaultdict(lambda: INF)
        self.dist[self.start] = 0

    def shortest_path_to_goal(self):
        self.init_dist()
        pq = [(self.dist[(r, c)], (r, c))
              for r, c in itertools.product(range(self.height), range(self.width))]
        heapq.heapify(pq)
        while pq:
            (_, (r0, c0)) = heapq.heappop(pq)
            if (r0, c0) == self.goal:
                break
            for dr, dc in DELTA:
                (r, c) = (r0 + dr, c0 + dc)
                if r < 0 or r >= self.height or c < 0 or c >= self.width:
                    continue
                else:
                    if (not self.stage[r0][c0]) and (not self.stage[r][c]):
                        cost = 1
                    else:
                        cost = 0
                    new_length = self.dist[(r0, c0)] + cost
                    if new_length < self.dist[(r, c)]:
                        self.dist[(r, c)] = new_length
                        heapq.heappush(pq, (new_length, (r, c)))
        return self.dist[self.goal]


def main():
    sys.setrecursionlimit(10000)
    f = lambda c: c == "."
    w, h = map(int, input().split())
    stage = [array.array("B", map(f, input())) for _ in range(h)]
    dfs = RecursiveDepthFirstSearch(w, h, copy.deepcopy(stage))
    start, goal = dfs.find_hollow_representatives()
    dij = Dijkstra(w, h, stage, start, goal)
    print(dij.shortest_path_to_goal() + 1)


if __name__ == '__main__':
    main()
0