• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jan 19th, 2020 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. struct LevelNode {
2.     int i;
3.     int j;
4.     int k;
5. };
6.
7. struct Level{
8.     int distance;
9.     vector<LevelNode> nodes;
10. };
11.
12. class Solution {
13.     bool isValid(int i, int j, int n, int m){
14.         return i >= 0 && j >= 0 && i < n && j < m;
15.     }
16.
17. public:
18.     int shortestPath(vector<vector<int>>& grid, int k) {
19.         int n = grid.size();
20.         int m = n? grid[0].size() : 0;
21.         int di[4] = {0, 0, 1, -1};
22.         int dj[4] = {1, -1, 0, 0};
23.         queue<Level> q;
24.         vector<vector<vector<int>>> vis(n, vector<vector<int>>(m, vector<int>(k+1)));
25.         q.push({0, {{0, 0, k}}});
26.         while(q.size()){
27.             Level curLevel = q.front();
28.             q.pop();
29.             vector<LevelNode> nxtLvl;
30.             for(LevelNode node : curLevel.nodes){
31.                 if(node.i == n-1 && node.j == m-1)
32.                     return curLevel.distance;
33.                 if(!isValid(node.i, node.j, n, m) || vis[node.i][node.j][node.k])
34.                     continue;
35.                 vis[node.i][node.j][node.k] = 1;
36.                 for(int d = 0; d < 4; d++) {
37.                     int ni = node.i + di[d];
38.                     int nj = node.j + dj[d];
39.                     if(isValid(ni, nj, n, m) && (!grid[ni][nj] || grid[ni][nj] == 1 && node.k))
40.                         nxtLvl.push_back({ni,nj,node.k-grid[ni][nj]});
41.                     }
42.             }
43.             if(nxtLvl.size())
44.                 q.push({curLevel.distance+1, nxtLvl});
45.         }
46.         return -1;
47.     }
48. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top