# Untitled

a guest
Jan 19th, 2020
80
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. map<pair<int, int>, int> nextLevelK;
31. for(LevelNode node : curLevel.nodes){
32.
33. if(node.i == n-1 && node.j == m-1)
34. return curLevel.distance;
35. if(!isValid(node.i, node.j, n, m) || vis[node.i][node.j][node.k])
36. continue;
37. vis[node.i][node.j][node.k] = 1;
38. for(int d = 0; d < 4; d++) {
39. int ni = node.i + di[d];
40. int nj = node.j + dj[d];
41. if(isValid(ni, nj, n, m) && grid[ni][nj] == 1 && node.k && !vis[ni][nj][node.k-1] ){
42. nextLevelK[{ni,nj}] = max(node.k-1, nextLevelK[{ni,nj}]);
43. }
44. else if(isValid(ni, nj, n, m) && !grid[ni][nj] && !vis[ni][nj][node.k]){
45. nextLevelK[{ni,nj}] = max(node.k, nextLevelK[{ni,nj}]);
46. }
47. }
48. }
49. for(auto it : nextLevelK)
50. nxtLvl.push_back({it.first.first, it.first.second, it.second});
51.
52. if(nxtLvl.size())
53. q.push({curLevel.distance+1, nxtLvl});
54. }
55. return -1;
56. }
57. };
RAW Paste Data