[金貨4]1261号:アルゴス駅
🛠 質問する
https://www.acmicpc.net/problem/1261
👩🏻💻 解決策
2665号:迷宮のような問題
BFSのみで問題を解決できるが,優先キュー(最小HIP)を用いて問題を解決する.
ソースコード
https://www.acmicpc.net/problem/1261
👩🏻💻 解決策
2665号:迷宮のような問題
BFSのみで問題を解決できるが,優先キュー(最小HIP)を用いて問題を解決する.
ソースコード
from heapq import heappush, heappop
m, n = map(int, input().split())
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
graph = []
visit = [[0] * m for i in range(n)]
for i in range(n):
graph.append(list(map(int, input())))
def dijkstra():
heap = []
heappush(heap, [0, 0, 0])
visit[0][0] = 1
while heap:
cnt, x, y = heappop(heap)
if x == n - 1 and y == m - 1:
print(cnt)
return
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] == 0:
heappush(heap, [cnt + 1 if graph[nx][ny] == 1 else cnt, nx, ny])
visit[nx][ny] = 1
dijkstra()
Reference
この問題について([金貨4]1261号:アルゴス駅), 我々は、より多くの情報をここで見つけました https://velog.io/@hyunnn/골드4-1261번-알고스팟テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol