백준 BOJ 14442 C++ 벽 부수고 이동하기 2

#include <bits/stdc++.h>
using namespace std;

int n, m, k, board[1002][1002], dist[1002][1002][12];

int di[] = {0, 0, 1, -1};
int dj[] = {1, -1, 0, 0};

queue<tuple<int, int, int>> q;

void solve() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) {
        string str;
        cin >> str;
        for (int j = 0; j < m; ++j) {
            board[i][j] = str[j] - '0';
        }
    }
    memset(dist, -1, sizeof(dist));
    dist[0][0][0] = 1;
    q.push({0, 0, 0});
    while (!q.empty()) {
        int i = get<0>(q.front());
        int j = get<1>(q.front());
        int cnt = get<2>(q.front());
        q.pop();
        if (i == n - 1 && j == m - 1) {  // 목표 지점에 도달한 경우, 조기 종료 / bfs 탐색 특성 상 빠르게 도착한 탐색 경로가 최단 경로
            cout << dist[i][j][cnt] << '\n';
            return;
        }
        for (int dir = 0; dir < 4; ++dir) {
            int ni = i + di[dir];
            int nj = j + dj[dir];
            if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
                // 현재 탐색에서 다음 이동 자리가 벽인데 벽을 부술 수 있고 아직 다른 탐색에 의해 방문되지 않은 경우
                if (board[ni][nj] == 1 && dist[ni][nj][cnt + 1] == -1 && cnt < k) {
                    dist[ni][nj][cnt + 1] = dist[i][j][cnt] + 1;
                    q.push({ni, nj, cnt + 1});
                
                // 현재 탐색에서 다음 이동 자리가 벽이 아니고 아직 다른 탐색 경로에서 방문되지 않은 경우
                } else if (board[ni][nj] == 0 && dist[ni][nj][cnt] == -1){
                    dist[ni][nj][cnt] = dist[i][j][cnt] + 1;
                    q.push({ni, nj, cnt});
                }
            }
        }
    }
    cout << -1 << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}