2178:迷宮


質問する



コード#コード#

#2718 : 미로탐색 
import sys
input = sys.stdin.readline
from collections import deque #BFS

m,n = map(int,input().split())

dx = [1,-1,0,0]
dy = [0,0,-1,1]

queue = deque() #칸수저장 
graph=[]

for i in range(m):
    graph.append(list(map(int, input().rstrip()))) 

#붙이기 

queue.append([0,0]) #0,0에서 출발 

def bfs():
  while queue:
      a,b = queue.popleft() #i.j삽입 
      for i in range(4):
          cx = a+dx[i]
          cy = b+dy[i]
          if 0<=cx<m  and 0<=cy<n and graph[cx][cy]==1: 
              graph[cx][cy] = graph[a][b] + 1 #칸수 더해나감 
              queue.append([cx,cy])
bfs()

print(graph[m-1][n-1])

解説


前のトマトの問題とあまり差がありません.
私はただ問題であなたに始まりと終わりを教えただけです.
キューを1つ作り、キューに過去のマス数を加えればいいので、スタートマスも含めてトマトと違って1を抜く必要はありません.