[アルゴリズム]BOJ 2178迷宮へナビゲート

[BOJ]178迷宫的导演卡

📍 質問する

N×Mサイズの配列として表現された迷路があります.

迷路では、1は移動可能なセル、0は移動不可能なセルを表します.これらの迷路が与えられた場合、(1,1)から(N,M)の位置に移動する際に通過しなければならない最小セル数を求めるプログラムを作成します.1つのセルから別のセルに移動する場合は、隣接するセルにのみ移動できます.
上記の例では、(N,M)の位置に移動するには15格子を通過しなければならない.数欄には、開始位置と到達位置も含まれます.

📍 入力

第1行は2つの整数N,M(2≦N,M≦100)を与える.次のN行には迷路としてM個の整数がある.各数を入力として加算します.

📍 しゅつりょく

出力は最初の行の最小セル数を通過する必要があります.常に到着位置まで移動できる場合のみ、入力として使用されます.

📍 に答える

ハーモニー

from collections import deque
from sys import stdin

N, M = map(int,stdin.readline().split())
maze = []
for _ in range(N):
  tmp = list(map(int,stdin.readline().rstrip()))
  for i in range(M):
    if tmp[i] == 1: tmp[i] = 10001 # 이동할 수 있는 칸의 값을 1에서 10001으로 변경
  maze.append(tmp)
D =  deque([[0, 0, 1]])

answer = 0
while D:
  [x, y, count] = D.popleft() # [ x좌표, y좌표, 이동 횟수 ]
  #  미로의 범위내 and 이동할 수 있는 칸 and 이동 횟수가 현재 이동할 칸의 값보다 작을 때
  if x - 1 >= 0 and maze[y][x-1] != 0 and maze[y][x-1] > count+1:
    D.append([x-1,y,count+1]) # BFS에 이동할 칸 추가
    maze[y][x-1] = count + 1 # 이동할 칸에 이동 횟수 입력
  if x + 1 < M and maze[y][x+1] != 0 and maze[y][x+1] > count +1:
    D.append([x+1,y,count+1])
    maze[y][x+1] = count + 1
  if y - 1 >= 0 and maze[y-1][x] != 0 and maze[y-1][x] > count +1:
    D.append([x,y-1,count+1])
    maze[y-1][x] = count + 1
  if y + 1 < N and maze[y+1][x] != 0 and maze[y+1][x] > count +1 :
    D.append([x,y+1,count+1])
    maze[y+1][x] = count + 1
print(maze[N-1][M-1]) # 도착지점의 이동횟수 값 출력