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を抜く必要はありません.
Reference
この問題について(2178:迷宮), 我々は、より多くの情報をここで見つけました
https://velog.io/@seochan99/2178-미로
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#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を抜く必要はありません.
Reference
この問題について(2178:迷宮), 我々は、より多くの情報をここで見つけました
https://velog.io/@seochan99/2178-미로
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
Reference
この問題について(2178:迷宮), 我々は、より多くの情報をここで見つけました https://velog.io/@seochan99/2178-미로テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol