• API
• FAQ
• Tools
• Archive
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;
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.

Top