算法1
(bfs) $O(mnk)$
带K标签的bfs,与bfs类似,visited数组要带MNK三个向量
C++ 代码
class Solution {
public:
typedef struct state{
int dis;
int x;
int y;
int k;
// bool operator<(const state M) const{
// return dis<M.dis;
// }
}state;
int shortestPath(vector<vector<int>>& grid, int k) {
int dx[4] = {0, 1 , 0,-1}, dy[4] = {1, 0, -1, 0};
int m = grid.size(), n = grid[0].size();
state beginstate = {0,0,0,k};
vector<vector<vector<bool>>> st(m,vector<vector<bool>>(n, vector<bool>(k+1,0)));
queue<state> q;
q.push(beginstate);
// vector<vector<bool>> st(m, vector<bool>(n,0));
// st[0][0] = 1;
// st.insert({0,0,k});
st[0][0][k] = 1;
while (!q.empty()){
state curr = q.front();
q.pop();
int d = curr.dis;
int x = curr.x;
int y = curr.y;
int k = curr.k;
// cout<<x<<' '<<y<<' '<<k<<endl;
if (x==m-1 && y == n-1) return d;
// st[x][y] = 1;
for (int i = 0;i<4;i++){
int xx = x + dx[i], yy = y + dy[i], kk = k;
if (xx>=0 && xx<m && yy>=0 && yy<n){
kk = k- grid[xx][yy];
if (kk>=0 && !st[xx][yy][kk]){
// st.insert({xx,yy,kk});
st[xx][yy][kk] = 1;
q.push({d+1, xx, yy, kk});
}
}
}
}
return -1;
}
};