[acmicpc] 14923. 미로 탈출(python)

벽 부수고 이동하기와 비슷한 유형의 문제이다.

import sys
from collections import deque
input=sys.stdin.readline

n,m=map(int,input().split())
hx,hy=map(int,input().split())
ex,ey=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
visit=[[1000]*m for _ in range(n)]
dirs=[(1,0),(0,1),(-1,0),(0,-1)]
q=deque()
q.append((hx-1,hy-1,0,0))
def bfs():
    while q:
        r,c,cnt,move=q.popleft()
        if r==ex-1 and c==ey-1:
            return move
        for i in range(4):
            nr,nc=r+dirs[i][0],c+dirs[i][1]
            if 0>nr or nr>=n or nc<0 or nc>=m: continue
            if visit[nr][nc]<cnt+1: continue
            if arr[nr][nc]:
                if cnt<1:
                    visit[nr][nc]=cnt+1
                    q.append((nr,nc,cnt+1,move+1))
            else:
                visit[nr][nc] = cnt
                q.append((nr, nc, cnt, move + 1))
    return -1
print(bfs())

---

https://www.acmicpc.net/problem/14923

14923번: 미로 탈출