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

struct Level{
    int distance;
    vector<LevelNode> nodes;
};

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<Level> q;
        vector<vector<vector<int>>> vis(n, vector<vector<int>>(m, vector<int>(k+1)));
        q.push({0, {{0, 0, k}}});
        while(q.size()){
            Level curLevel = q.front();
            q.pop();
            vector<LevelNode> nxtLvl;
            map<pair<int, int>, int> nextLevelK;
            for(LevelNode node : curLevel.nodes){

                if(node.i == n-1 && node.j == m-1)
                    return curLevel.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) && grid[ni][nj] == 1 && node.k && !vis[ni][nj][node.k-1] ){
                        nextLevelK[{ni,nj}] = max(node.k-1, nextLevelK[{ni,nj}]);
                    }
                    else if(isValid(ni, nj, n, m) && !grid[ni][nj] && !vis[ni][nj][node.k]){
                        nextLevelK[{ni,nj}] = max(node.k, nextLevelK[{ni,nj}]);
                    }
                }
            }
            for(auto it : nextLevelK)
                nxtLvl.push_back({it.first.first, it.first.second, it.second});

            if(nxtLvl.size())
                q.push({curLevel.distance+1, nxtLvl});
        }
        return -1;
    }
};