[ 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. 

[UVA] 10507 - Waking up brain

Problem Statement : 10507 - Waking up brain
Source            : UVA Online Judge
Category          : Graph Theory
Algorithm         : bfs
Verdict           : Accepted

#include<bits/stdc++.h>  
using namespace std;  
#define vi  vector<int>  
#define mx 30  
#define em emplace_back  
vi graph[mx];  
int on[mx];  
int dist[mx];  
int tnode,tedge;  
char str[4];  
set<int>used[mx];  
int toint(char ch){  
    return ch-'A'+1;  
}  
void init(){  
    for(int i=0;i<mx;i++){  
        graph[i].clear();  
        on[i]=0;  
        used[i].clear();  
    }  
}  
int bfs(int x,int y,int z){  
    on[x]=on[y]=on[z]=1;  
    queue<int>q;  
    q.emplace(x);  
    q.emplace(y);  
    q.emplace(z);  
    dist[x]=dist[y]=dist[z]=0;  
    int mxdist=0;  
    int visit=3;  
    while(!q.empty()){  
        int u=q.front();  
        q.pop();  
        for(int v:graph[u]){  
            if(on[v])continue;  
  
            used[v].emplace(u);  
  
            if(used[v].size()==3){  
                dist[v]=dist[u]+1;  
                if(dist[v]>mxdist)mxdist=dist[v];  
                on[v]=1;  
                visit++;  
                q.emplace(v);  
            }  
        }  
    }  
    if(visit<tnode) return -1;  
    return mxdist;  
}  
int main(){  
    //freopen("input.txt","r",stdin);  
    //freopen("output.txt","w",stdout);  
    while(cin>>tnode>>tedge){  
        init();  
        cin>>str;  
        int x=toint(str[0]);  
        int y=toint(str[1]);  
        int z=toint(str[2]);  
        cin.ignore();  
        for(int i=1;i<=tedge;i++){  
            cin>>str;  
            int u=toint(str[0]);  
            int v=toint(str[1]);  
            graph[u].em(v);  
            graph[v].em(u);  
        }  
        int year=bfs(x,y,z);  
  
        if(year==-1)cout<<"THIS BRAIN NEVER WAKES UP"<<endl;  
        else cout<<"WAKE UP IN, "<<year<<", YEARS"<<endl;  
    }  
  
    return 0;  
}