1293 障碍物的最短路径

请看经典题型。

class Solution {



    public:


vector<vector<int>> dir={{1,0},{-1,0},{0,-1},{0,1}};
    int shortestPath(vector<vector<int>>& grid, int k) {
int row=grid.size();
int col=grid[0].size();

priority_queue<vector<int>, vector<vector<int>>, greater<>> pq;
//node first=node({0,0,0,k});
k=min(k,row+col-3);
vector<int> first={0,0,0,k};
pq.push(first);

while(!pq.empty())
{
    vector<int> start=pq.top();
    pq.pop();

    if(start[1]==row-1&&start[2]==col-1)
    return start[0];

int k=start[3];
    for(int k=0;k<4;k++)
    {
        int i=start[1]+dir[k][0];
        int j=start[2]+dir[k][1];

if(i>=0&&i<row&&j>=0&&j<col)
{
    if(grid[i][j]==0)
    {
        pq.push({start[0]+1, i, j, start[3]});
    }

    else
    {
        if(start[3]>=1)
        pq.push({start[0]+1,i,j,start[3]-1});
    }
}



    }
}


return -1;


    }
};

用了广度遍历和贪心。结果超时。

没有超时的算法，也是广度遍历，
琢磨一下午没琢磨出来，是哪里超时了。。。
struct State {
    int x, y;
    int r;
    State(int x_, int y_, int r_) {
        x = x_;
        y = y_;
        r = r_;
    }
};

class Solution {
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
public:
    int shortestPath(vector<vector<int>>& g, int k) {
        int m = g.size(), n = g[0].size();
        if(k >= m + n - 3) return m + n - 2;
        vector<vector<vector<bool>>> visited(m, vector<vector<bool>>(n, vector<bool>(k + 1, 0)));
        queue<State> Q;
        Q.emplace(0, 0, k);
        int step = 0;
        while(!Q.empty()) {
            int s = Q.size();
            while(s--) {
                auto p = Q.front();
                Q.pop();
                int x = p.x, y = p.y;
                int r = p.r;
                if(x == m - 1 && y == n - 1 && r >= 0) return step;
                if(visited[x][y][r] == 1) continue;
                visited[x][y][r] = 1;
                for(int k = 0; k < 4; k++) {
                    if(x + dx[k] >= 0 && x + dx[k] < m && y + dy[k] >= 0 && y + dy[k] < n) {
                        if(g[x + dx[k]][y + dy[k]] == 1 && r >= 1) Q.emplace(x + dx[k], y + dy[k], r - 1);
                        else if(g[x + dx[k]][y + dy[k]] == 0)
                            Q.emplace(x + dx[k], y + dy[k], r);
                    }
                }
            }
            step++;
        }
        return -1;
    }
};


所以， 问题出在哪里？