벽을 한 번 없애고 도착해요

같은 칸에도 남은 기회가 다른 두 상태가 있어요

앞 BFS에서 위치마다 거리 한 개를 저장했어요. 이번에는 벽을 없애는 기회가 한 번 있어요. 벽을 이미 없애고 도착한 상태와 기회를 남긴 채 도착한 상태는 앞으로 갈 수 있는 칸이 달라요.

따라서 상태를 좌표 (r,c)만이 아니라 (r,c,used)로 정해요. used=0은 아직 기회를 사용하지 않음, 1은 이미 사용했음을 뜻해요. 거리표를 상태별로 두 겹 만들어요.

거리표의 겹과 큐의 세 값을 맞춰요

vector<vector<vector<int>>> dist(
    2, vector<vector<int>>(rows, vector<int>(cols, -1)));

첫 인덱스가 사용 상태이고 dist[used][r][c]가 그 상태로 도착한 거리예요. 큐의 {r,c,used}도 같은 정보를 가져요.

기회가 남은 상태로 조금 늦게 같은 칸에 도착하면 버려도 될까요? 뒤에 벽이 꼭 필요하면 그 상태만 끝에 갈 수 있어요. 좌표만 방문했다고 두 상태를 합치지 않아요.

사용은 선택 사항이에요

벽 없는 길이 있으면 기회를 쓰지 않고 도착해도 돼요. 두 도착 상태 중 이동 횟수가 더 작은 것이 답이에요. FIFO 큐는 모든 상태를 이동 횟수 순으로 처리하므로 목적지에서 처음 꺼낸 상태가 최단이에요.

벽을 없애는 행동은 그 벽 칸으로 이동하는 한 번에 포함해요. 추가 이동 비용은 없어요. 시작점과 끝점은 통로여서 1×1 격자는 여전히 이동 0번이에요.

직접 풀어봐요

0은 통로, 1은 벽인 grid에서 (0,0)부터 (rows−1,cols−1)까지 상하좌우로 이동해요. 경로 전체에서 벽 칸을 최대 한 개 없애 통과할 수 있어요. 최소 이동 횟수를 반환하고, 한 번을 써도 도착 불가면 −1이에요. 기회를 반드시 쓸 필요는 없어요.

행·열 수는 각각 1~12이며 모든 행의 길이는 같아요. 시작과 끝은 0이에요. 벽을 없애는 비용은 추가하지 않고 그 칸으로의 이동 한 번만 세요. 실행용 입력은 rows cols와 격자 값들, 출력은 반환값이에요. 하네스가 입출력을 처리해요.

예시 1: grid={{0,1,0}} → 2. 가운데 벽 한 개를 없애 두 번 이동해요. 예시 2: grid={{0,1,1,0}} → -1. 벽 두 개가 연속이라 한 번의 기회로는 통과 못 해요.

1 3
0 1 0

2

1 4
0 1 1 0

-1