daily pastebin goal
22%
SHARE
TWEET

Untitled

a guest Dec 16th, 2018 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct node
  2. {
  3.     int n;
  4.     int dist;
  5.     bool beenOnLadderBefore;
  6.     node(int N, int Dist, bool been)
  7.     {
  8.         n = N; dist = Dist; beenOnLadderBefore = been;
  9.     }
  10.     //operator overloading for priority queue comparison
  11.     bool operator>(const node &a) const
  12.     {
  13.         return (dist > a.dist);
  14.     }
  15. };
  16.  
  17.  
  18. class Solution {
  19. public:
  20.  
  21. int dijkstas(vector<vector<int>> &b)
  22. {
  23.     int s = 1;
  24.     int N = b.size();
  25.     int g = N*N;
  26.    
  27.     // {dist from the starting node, node}
  28.     priority_queue<node,vector<node>,greater<node>> nodes;
  29.     nodes.emplace(s,0,false);
  30.  
  31.     vector<vector<bool>> visited((N*N)+1,vector<bool>(2,false));
  32.     while(!nodes.empty())
  33.     {
  34.         auto current = nodes.top();
  35.         if(current.n == g)
  36.             return current.dist;
  37.         nodes.pop();
  38.         if(current.n > g || visited[current.n][current.beenOnLadderBefore]) continue;
  39.         visited[current.n][current.beenOnLadderBefore] = true;
  40.        
  41.         int r = N-1-((current.n-1)/N); int c = ((N-1-r)%2)==0 ? (current.n-1)%N : N-1-(current.n-1)%N;
  42.        
  43.         // visit each child, if not already visited
  44.         if(b[r][c]!=-1 && !current.beenOnLadderBefore)
  45.         {
  46.             nodes.emplace(b[r][c], current.dist, true);
  47.         }
  48.         else
  49.         {
  50.             for (int i = 1; i <= 6; ++i)
  51.             {
  52.                 nodes.emplace(current.n + i, current.dist+1, false);
  53.             }
  54.         }
  55.  
  56.     }
  57.  
  58.     return -1;
  59. }
  60.  
  61. int snakesAndLadders(vector<vector<int>>& board)
  62. {
  63.     return dijkstas(board);
  64. }
  65. };
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. OK, I Understand
 
Top