1293

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int n = grid.size(), m = grid[0].size();
        bool vis[n][m][k+1];
        memset(vis, 0, sizeof(vis));

        queue<vector<int>> q;
        q.push({0,0,0});
        vis[0][0][0] = true;

        int dir[4][2] = {{-1,0}, {0,-1}, {0,1}, {1,0}};
        int steps = 0;
        while(!q.empty()){
            int sz = q.size();
            for(int i=0; i<sz; i++){
                auto p = q.front(); q.pop();
                int curX = p[0], curY = p[1], curK = p[2];
                if(curX == n-1 && curY == m-1)
                    return steps;

                for(int j=0; j<4; j++){
                    int nextX = curX+dir[j][0], nextY = curY+dir[j][1], nextK = curK;
                    if(nextX < 0 || nextX >= n || nextY < 0 || nextY >=  m) continue;
                    if(grid[nextX][nextY]) nextK++;
                    if(nextK > k || vis[nextX][nextY][nextK]) continue;
                    vis[nextX][nextY][nextK] = true;
                    q.push({nextX, nextY, nextK});
                }
            }
            steps++;
        }
        return -1;
    }
};