[白俊]探索2178迷宮(Python)

7307 ワード
BFS テキストリンク

質問する


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

入力


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

しゅつりょく


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

に答える







コード#コード#


a,b = map(int,input().split())

li=[]
for _ in range(a):
    li.append(list(map(int, input())))

from collections import deque
dx = [0,0,-1,1]  // 상하좌우
dy = [-1,1,0,0]

queue = deque()
queue.append((0, 0))

while queue:
    r, c = queue.popleft()
    for i in range(4): // 상하좌우 탐색
        ny = r + dy[i]
        nx = c + dx[i]

        if nx < 0 or nx >= b or ny < 0 or ny >= a or li[ny][nx]==0:
            continue
        if li[ny][nx]==1: // 탐색을 진행하지 않은 노드일때
            li[ny][nx] = li[r][c]+1 // 이전노드 거리에 +1한 값을 넣어준다
            queue.append((ny, nx))
            
print(li[a-1][b-1])
Codility-lesson9
jsにおける配列とオブジェクトのコピー