結果

問題 No.157 2つの空洞
ユーザー kichirb3kichirb3
提出日時 2018-03-10 10:48:36
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 2,741 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 10,932 KB
実行使用メモリ 8,672 KB
最終ジャッジ日時 2023-08-03 00:27:11
合計ジャッジ時間 2,038 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
8,388 KB
testcase_01 AC 16 ms
8,468 KB
testcase_02 AC 16 ms
8,524 KB
testcase_03 AC 16 ms
8,532 KB
testcase_04 AC 15 ms
8,532 KB
testcase_05 AC 16 ms
8,488 KB
testcase_06 AC 16 ms
8,496 KB
testcase_07 AC 17 ms
8,376 KB
testcase_08 AC 15 ms
8,400 KB
testcase_09 AC 15 ms
8,484 KB
testcase_10 AC 16 ms
8,324 KB
testcase_11 AC 15 ms
8,556 KB
testcase_12 AC 16 ms
8,272 KB
testcase_13 AC 17 ms
8,408 KB
testcase_14 AC 18 ms
8,600 KB
testcase_15 AC 16 ms
8,592 KB
testcase_16 AC 16 ms
8,608 KB
testcase_17 AC 16 ms
8,492 KB
testcase_18 AC 16 ms
8,672 KB
testcase_19 AC 16 ms
8,516 KB
権限があれば一括ダウンロードができます

ソースコード

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