Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- 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] || grid[ni][nj] == 1 && node.k))
- nxtLvl.push_back({ni,nj,node.k-grid[ni][nj]});
- }
- }
- if(nxtLvl.size())
- q.push({curLevel.distance+1, nxtLvl});
- }
- return -1;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement