[白俊14461]牛が道を渡る理由7

12637 ワード
パイ 金貨。 アルゴリズム#アルゴリズム# 白駿 コーディングテスト テキストリンク

1.問題の説明


牛が道を渡る理由

2.問題分析


複数のアルゴリズムで移動回数を計算し、草を食べるときを選択できます.
  • が開始されると、移動のカウントが3の倍数であればノード値が追加され、残りはtが追加される.この場合、更新が不正確(3の倍数の前にtのケースを加えると最高価格なので、ちゃんと更新していない)、草を食べる時も残りの場合も扱いにくいです.数十分悩んだ後に検索してみると、最初から3の倍数のように草食を基準に次の料金が選べます.現在の位置がマンハッタン通りで、到着地と2以下の場合、最高価格を更新すれば、答えが得られます.1回移動するたびに、3の倍数のように料金を処理します.何度も移動できるからです.ちょっと考えろ...!

    • 3.私の回答

    import sys
import heapq

INF = sys.maxsize
n, t = map(int, sys.stdin.readline().rstrip().split())
nodes = []
for _ in range(n):
    line = list(map(int, sys.stdin.readline().rstrip().split()))
    nodes.append(line)

dx = [0, 0, 1, -1, 0, 1, 2, 3, 2, 1, 0, -1, -2, -3, -2, -1]
dy = [1, -1, 0, 0, 3, 2, 1, 0, -1, -2, -3, -2, -1, 0, 1, 2]
# 1칸 이동 + 3칸 이동 offset

def Dijkstra():
    distances = [[INF for _ in range(n)] for _ in range(n)]
    distances[0][0] = 0
    pq = []
    heapq.heappush(pq, [0, 0, 0, 0])
    answer = INF
    while pq:
        cur_cost, cur_row, cur_col, cur_cnt = heapq.heappop(pq)

        if distances[cur_row][cur_col] < cur_cost: continue

        up_to_n = abs(n-1-cur_row) + abs(n-1-cur_col)
        if up_to_n <= 2:
            answer = min(answer, cur_cost + up_to_n*t)
            # 3칸 뛰지 않아도(즉 풀을 먹지 않아도) 될 때 최솟값 갱신

        for x, y in zip(dx, dy):
            next_row, next_col = cur_row + y, cur_col + x
            if next_row < 0 or next_col < 0 or next_row >= n or next_col >= n: continue
            next_cost = 3*t + nodes[next_row][next_col]
            # 풀을 먹을 때 거리

            if distances[next_row][next_col] > next_cost + cur_cost:
                distances[next_row][next_col] = next_cost + cur_cost
                heapq.heappush(pq, [next_cost + cur_cost, next_row, next_col, cur_cnt + 1])
    return answer

ans = Dijkstra()
print(ans)
    [Java]伯俊2447号[星を撮る-10]Java
    JavaScriptの自動変換