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

struct State {
    int x, y, removed, dist;
};

int shortestPathWithRemovals(vector<vector<int>>& grid, int k) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<vector<bool>>> visited(n, vector<vector<bool>>(m, vector<bool>(k + 1, false)));

    queue<State> q;
    q.push({0, 0, 0, 0});
    visited[0][0][0] = true;

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    while (!q.empty()) {
        auto [x, y, removed, dist] = q.front();
        q.pop();

        if (x == n - 1 && y == m - 1) return dist;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

            int newRemoved = removed + grid[nx][ny]; // remove wall if present
            if (newRemoved <= k && !visited[nx][ny][newRemoved]) {
                visited[nx][ny][newRemoved] = true;
                q.push({nx, ny, newRemoved, dist + 1});
            }
        }
    }
    return -1; // no path
}

int main() {
    vector<vector<int>> grid = {
        {0, 1, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 1, 0},
        {1, 1, 1, 1, 0},
        {0, 0, 0, 0, 0}
    };
    int k = 1; // allow removal of 1 wall

    cout << shortestPathWithRemovals(grid, k) << endl;
    return 0;
}