結果

問題 No.157 2つの空洞
コンテスト
ユーザー kichirb3
提出日時 2018-03-10 10:48:36
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 32 ms / 2,000 ms
コード長 2,741 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-10-12 22:35:29
合計ジャッジ時間 1,877 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

# -*- coding: utf-8 -*-
"""
No.157 2つの空洞
https://yukicoder.me/problems/no/157

"""
import sys
from sys import stdin
from heapq import heappush, heappop
input = stdin.readline

def prepare_graph(maze, W, H):
    #  あるマスから上下左右のマスへの移動コストを計算する。(壁であればコスト1、空洞であればコスト0)
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    adj = [[] for _ in range(H*W)]
    for y in range(1, H-1):     #  外周部は常に壁なので、起点から省略する
        for x in range(1, W-1):
            for i in range(len(dy)):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 < nx < W-1 and 0 < ny < H-1:
                    from_node = W*y + x
                    to_node = W*ny + nx
                    cost = 1
                    if maze[ny][nx] == '.':
                        cost = 0
                    adj[from_node].append([to_node, cost])
    return adj


def dijkstra(adj, s):
    # ダイクストラ法で始点からの距離を計算する
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * len(adj)
    d = [float('inf')] * len(adj)    # 始点からの距離 計算結果
    d[s] = 0                    #  始点から自身までの距離は0
    pq = []
    heappush(pq, (0, s))
    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue
        for v, cost in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + cost:
                d[v] = d[u] + cost
                heappush(pq, (d[v], v))
                color[v] = GRAY
    return d                    #  計算した距離情報を返す


def solve(maze, W, H):
    adj = prepare_graph(maze, W, H) #  迷路の隣接リストを作成

    # どこかの'.'を起点にして、他のマスへの移動コストを計算
    found = False
    start_node = 0              #  探索起点のノード番号
    for y in range(1, H-1):
        if found:
            break
        for x in range(1, W-1):
            if maze[y][x] == '.':
                found = True
                start_node = W*y + x
                break

    dist = dijkstra(adj, start_node)

    for y in range(1, H-1):
        for x in range(1, W-1):
            ans = dist[W*y + x]
            if ans != 0 and maze[y][x] != '#': #  移動コストが0以外で壁でなければ、他の空洞に属しているマス
                return ans


def main(args):
    W, H = map(int, input().split())
    maze = []
    for _ in range(H):
        maze.append(list(input().strip()))

    ans = solve(maze, W, H)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
0