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

🥚質問する

🥚入力/出力

🍳コード#コード#

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, list(input().strip()))) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 3차원 배열로 표현
# visited[r][c][0] -> 벽을 한 번도 안 뚫었을 때
# visited[r][c][1] -> 벽을 한번이라도 뚫었을 때
visited = [[[0] * 2 for _ in range(m)] for __ in range(n)]

# flag가 1일 때 -> 벽을 한 번이라도 뚫음
# flag가 0일 때 -> 벽을 한 번도 안 뚫음


def bfs(r, c, flag):
    q = deque([])
    q.append((r, c, flag))
    visited[r][c][flag] = 1

    while q:
        r, c, flag = q.popleft()
		
        """
        if flag == 0:
            print("벽을 파괴하지 않은", end=' ')
        else:
            print("벽을 파괴한", end=' ')
        print("(", r, ",", c, ")", "에서 탐색한 결과")
        """

        for i in range(4):
            new_r = r + dx[i]
            new_c = c + dy[i]

            if 0 <= new_r < n and 0 <= new_c < m:
                if arr[new_r][new_c] == 0:
                    if visited[new_r][new_c][flag] == 0:
                        visited[new_r][new_c][flag] = visited[r][c][flag] + 1
                        q.append((new_r, new_c, flag))
                else:
                    if flag == 0:
                        #print("(", new_r, ",", new_c, ") 에서 벽을 파괴")
                        visited[new_r][new_c][1] = visited[r][c][0] + 1
                        q.append((new_r, new_c, 1))

        """
        for row in visited:
            print(row)
        print('='*20)
        """

# bfs 실행
bfs(0, 0, 0)

# 출력
if 0 in visited[n-1][m-1]:
    min_dist = max(visited[n-1][m-1][0], visited[n-1][m-1][1])
else:
    min_dist = min(visited[n-1][m-1][0], visited[n-1][m-1][1])

if min_dist == 0:
    print(-1)
else:
    print(min_dist)

🧂アイデア

BFS

壁を破った問題をどう表現しますか?
1つ目のアイデアは、「壁がまだ破れていない場合、壁が破壊されたことを示し、その点でbfsを再実行する」(時間の複雑さを考慮してコードを記述する必要がある)

回のアクセスを3 Dリストにまとめることで、破壁を表示できます.

訪問[r][c][0]:世界(r,c)から壁を破壊したことのない距離

アクセス[r][c][1]:世界(r,c)から一度壁を破壊した(r,c)移動距離

アクセス更新方法

arr[new r][new c]が0の場合

0に移動可能で、flagに限定されません.

visited[new_r][new_c][flag]= visited[r][c][flag] + 1

arr[new r][new c]が1の場合

未破壁(flag=0)の場合、

を移動することができる.

visited[new_r][new_c][1] = visited[r][c][0] + 1

flagを1に更新!

(例)
2 2
01
10
(r,c)毎にbfsが出力されると、🔽

벽을 파괴하지 않은 ( 0 , 0 ) 에서 탐색한 결과
( 1 , 0 ) 에서 벽을 파괴
( 0 , 1 ) 에서 벽을 파괴
[[1, 0], [0, 2]]
[[0, 2], [0, 0]]
====================
벽을 파괴한 ( 1 , 0 ) 에서 탐색한 결과
[[1, 3], [0, 2]]
[[0, 2], [0, 3]]
====================
벽을 파괴한 ( 0 , 1 ) 에서 탐색한 결과
[[1, 3], [0, 2]]
[[0, 2], [0, 3]]
====================
벽을 파괴한 ( 0 , 0 ) 에서 탐색한 결과
[[1, 3], [0, 2]]
[[0, 2], [0, 3]]
====================
벽을 파괴한 ( 1 , 1 ) 에서 탐색한 결과
[[1, 3], [0, 2]]
[[0, 2], [0, 3]]
====================

ヘルプ投稿:★☆☆★[必読]壁を破って移動するFAQ★☆★★★