BOJ 13903 출근(Python 3)

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

푸는 방법은 간단합니다.

1. 1행에 있는 C개의 열을 전부 큐에 집어 넣고, BFS를 돌립니다.

2. BFS를 다 돌린 후, R행에서 최솟값을 구합니다.

파이썬은 까딱하면 시간 초과가 나오니까 Pypy3으로 제출하는게 좋습니다.

코드확인

from collections import deque
n,m=map(int,input().split())
D=[list(map(int,input().split())) for _ in range(n)]
S=[[-1]*m for _ in range(n)]
k=int(input())
dx,dy=[0]*k,[0]*k
for i in range(k):
    x,y=map(int,input().split())
    dx[i],dy[i]=x,y
q=deque()
ans=10**6
for i in range(m):
    if D[0][i]==1:
        q.append((0,i))
        S[0][i]=0
while q:
    x,y=q.popleft()
    for i in range(k):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m and D[nx][ny]==1 and S[nx][ny]==-1:
            q.append((nx,ny))
            S[nx][ny]=S[x][y]+1
for i in range(m):
    if D[n-1][i]==1 and S[n-1][i]!=-1:
        ans=min(ans,S[n-1][i])
print([ans,-1][ans==10**6])