[B14442]-벽 부수고 이동하기2

이번에는 벽 부수고 이동하기1에 이어 벽 부수고 이동하기 2입니다.

부술 수 있는 벽의 개수가 입력으로 주어지는 것이 차이점입니다.

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

#include <cstdio>
#include <queue>
using namespace std;
int a[1001][1001] = { 0, };
int d[1001][1001][11] = { 0, };
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
int main()
{
    int n, m,k;
    int ans=1000000000;
    scanf("%d %d %d", &n, &m, &k);
    queue<pair<pair<int, int>, int>>q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            scanf("%1d", &a[i][j]);
    }
    q.push({ {0,0},0 });
    d[0][0][0] = 1;
    while (!q.empty())
    {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int z = q.front().second;
        q.pop();
        for (int as = 0; as < 4; as++)
        {
            int nx = x + dx[as];
            int ny = y + dy[as];
            if (nx >= 0 && nx < n&&ny >= 0 && ny < m&&z<=k)
            {
                if (a[nx][ny] == 0 && d[nx][ny][z] == 0)
                {
                    d[nx][ny][z] = d[x][y][z] + 1;
                    q.push({ { nx,ny }, z });
                }
                else if (a[nx][ny] == 1 && z+1 <= k && d[nx][ny][z + 1] == 0)
                {
                    d[nx][ny][z + 1] = d[x][y][z] + 1;
                    q.push({ {nx,ny},z + 1 });
                }
            }
        }
    }
    for (int i = 0; i <= k; i++)
    {
        if (d[n - 1][m - 1][i] == 0)
            continue;
        if(d[n - 1][m - 1][i] < ans)
            ans = d[n - 1][m - 1][i];
    }
    if (ans == 1000000000)
        ans = -1;
 
    printf("%d\n", ans);
    return 0;
}