struct LevelNode {
    int i;
    int j;
    int k;
};


class Solution {
    bool isValid(int i, int j, int n, int m){
        return i >= 0 && j >= 0 && i < n && j < m;
    }

public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int n = grid.size();
        int m = n? grid[0].size() : 0;
        int di[4] = {0, 0, 1, -1};
        int dj[4] = {1, -1, 0, 0};
        queue<pair<LevelNode, int>> q;
        vector<vector<vector<int>>> vis(n, vector<vector<int>>(m, vector<int>(k+1)));
        q.push({{0, 0, k},0});
        while(q.size()){
            LevelNode node = q.front().first;
            int distance = q.front().second;
            q.pop();
            if(node.i == n-1 && node.j == m-1)
                return distance;
            if(!isValid(node.i, node.j, n, m) || vis[node.i][node.j][node.k])
                continue;
            vis[node.i][node.j][node.k] = 1;
            for(int d = 0; d < 4; d++) {
                int ni = node.i + di[d];
                int nj = node.j + dj[d];
                if(isValid(ni, nj, n, m)){
                    if(!grid[ni][nj])
                        q.push({{ni,nj,node.k}, distance+1});
                    else if(grid[ni][nj] == 1 && node.k)
                        q.push({{ni,nj,node.k-grid[ni][nj]}, distance+1});
                }
            }
        }
        return -1;
    }
};