22032-地形移動

◾地形移動：プログラマーLEVEL 4

https://programmers.co.kr/learn/courses/30/lessons/62050

質問する

正四角形の地形があり、大きさはN x Nです.各グリッドのサイズは1 x 1で、各グリッドには数字があります.グリッドの数値は、グリッドの高さを表します.
この地形の任意の格子から出発して、すべての格子を訪問する探検に行きます.セルを移動するときは、上、下、左、右に1つのセルを移動できます.現在のセルと移動するセルの高さの差はheightより小さくなければなりません.高さ差がheightより大きい場合は、梯子を取り付けて移動できます.梯子を取り付けるコストは、2つのメッシュの高さ差と等しい.そのため、すべての部屋に最小限のコストで移動できるように梯子を取り付ける必要があります.取り付け可能な梯子の数は制限されず、取り付けられた梯子は取り外されません.
各グリッドの高さを含む2 D舗装土地と移動可能な最大高さ差の高さをパラメータとして指定した場合、すべてのグリッドにアクセスするために必要な梯子設置費用の最大値を返すソルバを完了します.

入力

landは、N x Nサイズの2次元アレイである.

陸地の最小サイズは4 x 4、最大サイズは300 x 300.

landの要素は各メッシュの高さを表す.

メッシュの高さが1以上10000以下の自然数.

heightは1以上10000以下の自然数です.

しゅつりょく

梯子取り付けの最低コスト

I/O例

landheightanswer[[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]]315[[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]]118

のり付け

1.解説

hipを使用して、移動費用(設置費用)を最小経路に移動し、設置費用を求めればよい.

[コスト、行座標、列座標]

最小お尻は、料金基準で小さいところから移動します.

BFS(またはDFS)により最短距離の一般的な問題の変形を探し、移動方向に関係なく設置費用のみを確認する.

2.プログラム

n、visit point、heap point初期化

n:土地の大きさ

visit point:アクセス座標

heap point:現在の可動座標を含む最小hip

エリア全体にアクセスする前に、インストールコストが最も低いエリアを繰り返しチェック

[コスト,r,c]:[コスト,行座標,列座標]

アクセスされた座標であれば経路、非アクセス座標の追加費用

上、下、左、右中可動座標

高差が高さを下回る料金は0、超えると差額となる料金

# 코드
import heapq
def solution(land, height):
    answer = 0
    n = len(land)
    visit_point = [[False] * n for _ in range(n)]
    
    heap_point = [[0, 0, 0]]
    while heap_point:
        cost, r, c = heapq.heappop(heap_point)
        if visit_point[r][c] == True:
            continue
        visit_point[r][c] = True
        answer += cost

        for d_r, d_c in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            new_r, new_c = r+d_r, c+d_c
            
            if new_r < 0 or new_r >= n or new_c < 0 or new_c >= n or visit_point[new_r][new_c] == True:
                continue

            new_cost = abs(land[r][c] - land[new_r][new_c])
            if new_cost <= height:
                new_cost = 0

            heapq.heappush(heap_point, [new_cost, new_r, new_c])

    return answer