Guest User

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