壁を破壊して移動

出典:白駿#2206
タイムアウトメモリ制限2秒192 MB

質問する

N×Mのマトリックス表現のマッピングがあります.地図では、0は移動可能な位置、1は移動不可能な壁の位置を示す.(1,1)から(N,M)の位置に移動し、最短経路に移動します.最短パスとは、地図上の最小セルを通るパスで、開始セルと終了セルが含まれます.
移動中に壁を割ったり移動したりする経路がもっと短い場合は、壁を割って移動することができます.
1つのセルで移動できるセルは上下左右に隣接するセルです.
地図を指定すると、最短パスを解くプログラムが作成されます.

入力

第1行はN(1≦N≦1000),M(1≦M≦1000)を与える.次のN行はMの数字で地図を与えます.(1,1)と(N,M)は常に0であると仮定する.

しゅつりょく

1行目に最短距離を出力します.不可能な場合は-1を出力します.

I/O例

入力例1

6 4
0100
1110
1000
0000
0111
0000

サンプル出力1

15

入力例2

4 4
0111
1111
1111
1110

サンプル出力2

-1

に答える

思考と解答説明

BFSでアクセスします.

最初は、アクセスを2次元配列に設定し、レプリケーション(再帰ではない)を続行し、次のキューに配置し、長さ(d)を1ずつ増やします.

crashの初期値は1に設定されており、壁(1)に遭遇したときに破壊できるcountとして設定されている.

この問題は、レプリケーション配列によって時間の複雑さが増加し、タイムアウトを招くことです.(deepcopyはスライスに比べて時間がかかります.-要素をコピーするだけでなく、すべての属性をコピーします)

次の参考資料を見て、コードを書き直しました.
参考資料

アクセスを3 D配列に設定します.

# visited
n = 6, m = 4
[[[0, 0], [0, 0], [0, 0], [0, 0]], 
[[0, 0], [0, 0], [0, 0], [0, 0]], 
[[0, 0], [0, 0], [0, 0], [0, 0]], 
[[0, 0], [0, 0], [0, 0], [0, 0]], 
[[0, 0], [0, 0], [0, 0], [0, 0]], 
[[0, 0], [0, 0], [0, 0], [0, 0]]]

アクセス・ケースの[0, 0]の最初の要素は、壁を破壊しないときに距離を記録します.2番目の要素は、壁を壊すときに距離を記録します.

matrixの要素が壁でない場合、(0)visited[nx][ny][crash]で値をvisited[x][y][crash]+1に設定します.崩壊回数が1であれ0であれ.

matrixの要素が壁である場合、(1)クラッシュ回数が0の場合にのみ、値がvisited[nx][ny][crash+1]に設定されます.

アクセス者を3 D配列に設定することは理解できません

実は、私が最初に思った答えと論理はあまり違いはないと思いますが、時間の複雑さを考慮していないので、タイムアウトしか発生しません.

同じbfsでも時間の複雑さは千差万別である可能性があることに気づく.

Python code (python3 - BFS)

# 백준 2206번 벽 부수고 이동하기
from sys import stdin
from collections import deque
import copy
input = stdin.readline

# n, m, matrix 입력받기
n, m = map(int, input().split())
matrix = []
one = []
final_one = []
for i in range(n):
    string = input().rstrip()
    temp = []
    for j in range(len(string)):
        s = int(string[j])
        temp.append(s)
        if s == 1:
            one.append((i, j))
    matrix.append(temp)

# 동 남 서 북
dx = [0, +1, 0, -1]
dy = [+1, 0, -1, 0]
start = (0, 0, 0)   # x = 0, y = 0, d = 1, crash = 0
def bfs(start):
    answer = int(1e9)
    global matrix
    # global visited
    visited = [[[0]*2 for _ in range(m)]for _ in range(n)]
    visited[0][0][0] = 1
    q = deque([start])
    while q:
        x, y, crash= q.popleft()
        if x == n-1 and y == m-1:
            answer = min(answer, visited[x][y][crash])               
            return answer
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if matrix[nx][ny] == 0 and visited[nx][ny][crash] == 0:
                    q.append((nx, ny, crash))
                    visited[nx][ny][crash] = visited[x][y][crash] + 1
                elif matrix[nx][ny] == 1 and crash == 0: 
                    q.append((nx, ny, crash+1))
                    visited[nx][ny][crash+1] = visited[x][y][crash] + 1   
    return False

result = bfs(start)
if result:
    print(result)
else:
    print(-1)