[ URI ] 1910 - Help Clotilde

Author            : Anwar Jahid Ruman Hossain 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : [ URI ] 1910 - Help Clotilde
Source            : URI Online Judge
Category          : Graph Theory
Algorithm         : BFS
Verdict           : Accepted

1. #include<bits/stdc++.h>  
2. using namespace std;  
3. #define ll long long int  
4. #define mx 100000  
5. #define inf 1<<30  
6. #define endl '\n'  
7. int channels[mx+5];  
8. int mov[mx+5];  
9. bool isValid(int id,int cnt){  
10.     if(id>=1 && id<=mx && channels[id]==1 && cnt<mov[id]){  
11.         mov[id]=cnt;  
12.         return true;  
13.     }  
14.     return false;  
15. }  
16. int bfs(int o,int d){  
17.     queue<pair<int,int> >q;  
18.     pair<int,int>s;  
19.     s.first=o;  
20.     s.second=0;  
21.     q.push(s);  
22.     mov[s.first]=0;  
23.     while(!q.empty()){  
24.         pair<int,int>a=q.front();  
25.         q.pop();  
26.         if(a.first==d)return a.second;  
27.         if(isValid(a.first+1,a.second+1))q.push(make_pair(a.first+1,a.second+1));  
28.         if(isValid(a.first-1,a.second+1))q.push(make_pair(a.first-1,a.second+1));  
29.         if(isValid(a.first*3,a.second+1))q.push(make_pair(a.first*3,a.second+1));  
30.         if(isValid(a.first*2,a.second+1))q.push(make_pair(a.first*2,a.second+1));  
31.         if(a.first%2==0){  
32.             if(isValid(a.first/2,a.second+1))q.push(make_pair(a.first/2,a.second+1));  
33.         }  
34.     }  
35.     return -1;  
36. }  
37. int main(){  
38.    // freopen("input.txt","r",stdin);  
39.     //freopen("output.txt","w",stdout);  
40.     int o,d,k,banned;  
41.     while(cin>>o>>d>>k){  
42.         if(o==0 && d==0 && k==0)break;  
43.         for(int i=1;i<=mx;i++){  
44.             channels[i]=1;  
45.             mov[i]=inf;  
46.         }  
47.         while(k--){  
48.             cin>>banned;  
49.             channels[banned]=0;  
50.         }  
51.         cout<<bfs(o,d)<<endl;  
52.     }  
53.     return 0;  
54. }  

                             

Input o d k } input channels 3 4 8 5 2           Channels[1-mx]=1             mov[1-mx]= INF             channels[4,5]=0             bfs(o,d) = bfs(3,8)             pair -> (3,0)      mov[3]=0	URI Help Clotilde 1910	Queue √  3 , 0 √  2 , 1 (3,0)  9 , 1  6 , 1  3 , 2 (2,1)  1 , 2  6 , 2  1 , 2 10 , 2 (9,1)  8 , 2

Queue	+1	-1	*3	*2	/2	Next Queue
(3,0)	(4,1)	(2,1)	(9,1)	(6,1)	(odd)	(2,1)
(2,1)	(3,2)	(1,2)	(6,2)	(4,2)	(1,2)	(9,1)
(9,1)	(10,2)	(8,2)	Break target channel d==8 so required move is 2

                                                                                                                                                                   

Approach:

1.     Valid channel এর value 1 সেট করি। এবং Invalid channel এর value 0 সেট করি।

2.     Mov[ ] এর সব index এর value INF সেট করি।    

3.     BFS এ  current channel এবং  starting mov Zero pair হিসেবে কিউ q তে পুশ করি।

4.     (+1,-1,*3,*2,/2) এর জন্য প্রতিবার  valid mov নিয়ে  q কিউ তে  update করি যতক্ষণ না  target channel  d না পাই , d পেলে এর জন্য প্রাপ্ত  mov রিটার্ন করি। এটাই Required Output.