結果

問題 No.157 2つの空洞
ユーザー はむ吉🐹はむ吉🐹
提出日時 2016-02-29 20:42:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 75 ms / 2,000 ms
コード長 2,818 bytes
コンパイル時間 1,096 ms
コンパイル使用メモリ 81,692 KB
実行使用メモリ 72,748 KB
最終ジャッジ日時 2023-10-24 19:13:18
合計ジャッジ時間 2,885 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 52 ms
61,180 KB
testcase_01 AC 51 ms
61,180 KB
testcase_02 AC 51 ms
61,180 KB
testcase_03 AC 52 ms
61,180 KB
testcase_04 AC 53 ms
63,236 KB
testcase_05 AC 52 ms
61,188 KB
testcase_06 AC 55 ms
63,232 KB
testcase_07 AC 52 ms
61,184 KB
testcase_08 AC 52 ms
61,184 KB
testcase_09 AC 54 ms
63,236 KB
testcase_10 AC 53 ms
61,184 KB
testcase_11 AC 57 ms
63,724 KB
testcase_12 AC 59 ms
63,712 KB
testcase_13 AC 60 ms
65,780 KB
testcase_14 AC 70 ms
68,480 KB
testcase_15 AC 75 ms
72,696 KB
testcase_16 AC 75 ms
72,748 KB
testcase_17 AC 74 ms
70,816 KB
testcase_18 AC 63 ms
65,936 KB
testcase_19 AC 69 ms
68,396 KB
権限があれば一括ダウンロードができます

ソースコード

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