Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- T.C O(N) ie. no. of blocks
- Logic:
- ->We will use bfs here.snl ie. snake and ladder map will keep track of
- snake and ladder from any block.
- ->visited array will keep track of visited block.
- ->queue will keep pairs where first will be block number and second will
- be no. of moves to go there.
- ->we have option to select 1 to 6 as we have control of dice so we
- iterated from current position upto 6 moves.
- */
- class Solution{
- public:
- int minThrow(int n, int arr[]){
- bool visited[30+1];
- memset(visited,false,sizeof(visited));
- map<int,int> snl;
- for(int i=0;i<2*n;i+=2){
- snl[arr[i]]=arr[i+1];
- }
- deque<pair<int,int>> q;
- q.push_back(make_pair(1,0));
- visited[1]=true;
- while(q.size()){
- pair<int,int> temp=q.front();
- q.pop_front();
- int pos=temp.first;
- int dist=temp.second;
- if(pos==30) return dist;
- for(int i=pos+1;i<=pos+6;i++){
- if(visited[i]==false){
- if(snl[i]){
- q.push_back(make_pair(snl[i],dist+1));
- visited[i]=true;
- }
- else{
- q.push_back(make_pair(i,dist+1));
- visited[i]=true;
- }
- }
- }
- }
- return 0;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement