アルゴ駅

白駿1261

Algospot運営チームが(N,M)に移動するために、少なくともどれだけの壁を破る必要があるかを求めた.

基地運営チームは迷宮に閉じ込められている.迷宮はNxMサイズで、1×1サイズの部屋からなっています.迷宮は空き部屋や壁で構成されており、空き部屋は自由に歩けますが、壁が破られなければ移動できません.

の小さなステーション運営チームが何人もいることは知っていますが、いつも同じ部屋にいなければなりません.つまり、何人かが別の部屋にいてはいけません.一部の部屋は移動可能で、上下左右に隣接する空き部屋です.

壁は普段は移動できませんが、アルゴス駅の武器AOJを使って壁を砕くことができます.壁を割ると空き部屋と同じ部屋になります.

現在(1、1)のAlgospot運営チームが(N、M)に移動する場合は、少なくともどれだけの壁を破る必要があるかを決定するプログラムを作成します.

の第1行は、迷路の大きさを表す横方向M、縦方向N(1≦N、M≦100)を与える.次のN行は迷路状態を表す数字0と1を与える.0は空き部屋、1は壁です.

(1,1)および(N,M)はしばしば貫通される.

にゅうしゅつりょく

入出力330111111034 2000 1100006 600110000010000011110000011010101000102

方法

:上下左右にナビゲートする場合、0の場合はappendleftを優先します.1は追加を表します.
このとき1は壁を破り,1を加えてアクセスを記録する

知るところ

優先キュー(hip)データ構造を使用できます.

コード#コード#

インデックスを使用したプール

from collections import deque
import sys

def bfs(maps, visited, n, m):
    visited[0][0] = 0
    q = deque()
    q.append((0,0))

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

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m:
                if visited[nx][ny] == -1 :
                    if maps[nx][ny] == 0:
                        visited[nx][ny] = visited[x][y]
                        q.appendleft((nx, ny))
                    else:
                        visited[nx][ny] = visited[x][y] + 1
                        q.append((nx, ny))
    return visited[-1][-1]
                
m, n = map(int, sys.stdin.readline().split())
maps = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
visited = [[-1]*m for _ in range(n)]
print(bfs(maps, visited, n, m))

お尻を利用した草

import heapq
import sys

def bfs():
    q = []
    heapq.heappush(q, [0, 0, 0])
    visited[0][0] = 1
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while q:
        w, x, y = heapq.heappop(q)

        if x==n-1 and y==m-1:
            return w

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m and visited[nx][ny] == 0:
                    heapq.heappush(q, (w+1 if maze[nx][ny] == 1 else w, nx, ny))
                    visited[nx][ny] = 1


m, n = map(int, sys.stdin.readline().split())
maze = [list(map(int, sys.stdin.readline().rstrip('\n'))) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
print(bfs())