Advertisement
imashutosh51

Snake and Ladder Problem

Aug 10th, 2022
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  1. /*
  2. T.C O(N) ie. no. of blocks
  3. Logic:
  4. ->We will use bfs here.snl ie. snake and ladder map will keep track of
  5.   snake and ladder from any block.
  6. ->visited array will keep track of visited block.
  7. ->queue will keep pairs where first will be block number and second will
  8.   be no. of moves to go there.
  9. ->we have option to select 1 to 6 as we have control of dice so we
  10.   iterated from current position upto 6 moves.
  11. */
  12.  
  13.  
  14. class Solution{
  15. public:
  16.     int minThrow(int n, int arr[]){
  17.         bool visited[30+1];
  18.         memset(visited,false,sizeof(visited));
  19.         map<int,int> snl;
  20.         for(int i=0;i<2*n;i+=2){
  21.             snl[arr[i]]=arr[i+1];
  22.         }
  23.         deque<pair<int,int>> q;
  24.         q.push_back(make_pair(1,0));
  25.         visited[1]=true;
  26.         while(q.size()){
  27.             pair<int,int> temp=q.front();
  28.             q.pop_front();
  29.             int pos=temp.first;
  30.             int dist=temp.second;
  31.             if(pos==30) return dist;
  32.             for(int i=pos+1;i<=pos+6;i++){
  33.                 if(visited[i]==false){
  34.                     if(snl[i]){
  35.                         q.push_back(make_pair(snl[i],dist+1));
  36.                         visited[i]=true;
  37.                     }
  38.                     else{
  39.                         q.push_back(make_pair(i,dist+1));
  40.                         visited[i]=true;
  41.                     }
  42.                 }
  43.             }
  44.            
  45.         }
  46.         return 0;
  47.     }
  48. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement