Category BFS

SPOJ – DIGOKEYS – Find the Treasure

Arunima Mandal Leave a comment

Problem Link: https://www.spoj.com/problems/DIGOKEYS/

Note: This problem is pretty much a simple Graph problem. I have solved this using BFS. One thing that I was confused about was how to handle the “lexicographically smallest order of path“. But after writing the basic code, the idea that came to my mind is how about if I sort the initial graph while building that by inserting the edge nodes. If the edges are sorted, then while running the BFS, it will automatically choose the smallest numbers first! That solves our finding of “lexicographically smallest order of path”. Please feel free to comment below if you have any other ideas to implement this.

Code:

#include <bits/stdc++.h>

using namespace std;

#define MAX 100005
int parent[MAX];

void path_print(int dst, int ans)
{
    vector<int> path;
    dst=parent[dst]; //As the question suggests not to include the last destination which is obvious in every case
    while(dst!=-1)
    {
        path.push_back(dst);
        dst=parent[dst];
    }
    cout<<path[ans-1];
    for(int i=ans-2; i>=0; i--) cout<<" "<<path[i];
    cout<<endl;
}


int bfs(int src, int dst, vector<vector<int> > &g)
{
    int vis[MAX]={0};
    int dis[MAX];
    vis[src]=1;
    dis[src]=0;
    parent[MAX]={-1};
    parent[src]=-1;
    queue<int> q;
    q.push(src);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(u==dst) return dis[u];
        for(int i=0; i<g[u].size(); i++)
        {
            int v=g[u][i];
            if(!vis[v])
            {
                vis[v]=1;
                dis[v]=dis[u]+1;
                parent[v]=u;
                q.push(v);
            }
        }
    }
    return -1;
}

int main()
{
    int t;
    cin>>t;
    for(int z=0; z<t; z++)
    {
        int n;
        cin>>n;
        vector<vector<int> > g(MAX, vector<int> (11));
        for(int j=1; j<n; j++)
        {
            int edge;
            cin>>edge;
            int src=j;
            vector<int> des; //for sorting the edges// for "lexicographical" purpose
            for(int k=0; k<edge; k++)
            {
                int dst;
                cin>>dst;
                des.push_back(dst);
            }
            sort(des.begin(), des.end()); //We are doing this only to ensure the "lexicographically smallest" order of path
            for(int k=0; k<des.size(); k++)
            {
                g[src].push_back(des[k]);
            }

        }
        int ans=bfs(1,n, g);
        cout<<ans<<endl;
        if(ans!=-1)
        {
            path_print(n, ans);
        }
        cout<<endl;
    }
    return 0;
}

UVa – 429 – Word Transformation

Arunima Mandal Leave a comment

In this problem, since there is no mention of limit of input in a particular test case, so we have assumed the empty string to be the termination. That’s why we have used getline() for taking input instead of cin. Otherwise there is no way of returning to another test case taking only string by cin.

#include <bits/stdc++.h>

#define ms(a,b)         memset(a,b,sizeof(a))
#define pb(a)           push_back(a)
#define db              double
#define ft              float
#define ll              long long
#define ull             unsigned long long
#define ff              first
#define ss              second
#define sz(x)           x.size()
#define qu              queue
#define pqu             priority_queue
#define vc              vector
#define vi              vector<int>
#define vll             vector<long long>
#define pii             pair<int,int>
#define pis             pair<int,string>
#define psi             pair<string,int>
#define all(x)          x.begin(),x.end()
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n)      for(int i=0;i<n;i++)
#define loop1(i,n)      for(int i=1;i<=n;i++)
#define stlloop(x)     for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)       __gcd(a, b)
#define lcm(a, b)       ((a)*((b)/gcd(a,b)))
#define case(z,x)       cout<<"Case "<<i<<": "<<x<<endl
#define case(z)         cout<<"Case "<<z<<": "
#define PI              3.14159265358979323846264338328
#define valid(tx,ty)    tx>=0 && tx<r && ty>=0 && ty<c
#define MAX             2000

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

using namespace std;

map<string,vector<string>> mp;

bool check(string a, string b)
{
    int cnt=0;
    if(sz(a)!=sz(b)) return 0;
    else
    {
        loop0(i,sz(a))
        {
            if(a[i]!=b[i]) cnt++;
            if(cnt>1) return 0;
        }
    }
    return cnt==1;
}

int bfs(string src, string dst)
{
    map<string,int>dis;
    map<string,bool>visited;
    queue<string>Q;
    Q.push(src);
    dis[src]=0;
    visited[src]=1;
    while(!Q.empty())
    {
        string u=Q.front();
        Q.pop();
        if(u==dst) return dis[u];
        loop0(i,sz(mp[u]))
        {
            string v=mp[u][i];
            if(!visited[v])
            {
                dis[v]=dis[u]+1;
                visited[v]=1;
                Q.push(v);
            }
        }
    }
}

int main()
{
//    CIN;
//    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int t;
    cin>>t;

    for(int z=1; z<=t; z++)
    {
        string str;
        vector<string>v;
        while(cin>>str  && str!="*") v.pb(str);
        loop0(i,sz(v))
        {
            for(int j=i+1; j<sz(v); j++)
                if(check(v[i],v[j]))
                {
                    mp[v[i]].pb(v[j]);
                    mp[v[j]].pb(v[i]);
                }
        }
        getchar();
        string s1;
        while(1)
        {
            getline(cin,s1);
            if(s1=="") break;
            bool x=0;
            string s3,s4;
            loop0(i,sz(s1))
            {
                if(s1[i]==' ')
                {
                    x=1;
                    continue;
                }
                if(!x)
                    s3+=s1[i];
                else
                    s4+=s1[i];
            }
            cout<<s3<<" "<<s4<<" "<<bfs(s3,s4)<<endl;
        }
        if(z!=t) cout<<endl;
        mp.clear();
    }
    return 0;
}

UVa – 762 – We Ship Cheap

Arunima Mandal Leave a comment 

#include <bits/stdc++.h>

#define ms(a,b)         memset(a,b,sizeof(a))
#define pb(a)           push_back(a)
#define db              double
#define ft              float
#define ll              long long
#define ull             unsigned long long
#define ff              first
#define ss              second
#define qu              queue
#define pqu             priority_queue
#define vc              vector
#define vi              vector<int>
#define vll             vector<long long>
#define pii             pair<int,int>
#define pis             pair<int,string>
#define psi             pair<string,int>
#define all(x)          x.begin(),x.end()
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n)      for(int i=0;i<n;i++)
#define loop1(i,n)      for(int i=1;i<=n;i++)
#define stlloop0(i,x)   for(int i=0;i<x.size();i++)
#define stlloop1(x)     for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)       __gcd(a, b)
#define lcm(a, b)       ((a)*((b)/gcd(a,b)))
#define PI              3.14159265358979323846264338328
#define MAX             2000

using namespace std;

bool visited[MAX];
int dis[MAX];
vector<int> g[MAX];
int parent[MAX];
int edge;
map<string,int> mp1;
map<int,string> mp2;

void path_print(int src,int dst)
{
    if(dst==src) return;
    path_print(src,parent[dst]);
    cout<<mp2[parent[dst]]<<" "<<mp2[dst]<<endl;
}

int bfs(int src,int dst)
{
    dis[src]=0;
    ms(visited,0);
    visited[src]=1;
    parent[src]=-1;
    qu<int> q;
    q.push(src);

    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0; i<g[u].size(); i++)
        {
            int v=g[u][i];
            if(!visited[v])
            {
                parent[v]=u;
                visited[v]=1;
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    if(visited[dst]) path_print(src,dst);
    else cout<<"No route"<<endl;
}

int main()
{
    CIN;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    bool test=0;
    while(cin>>edge)
    {
        if(test) cout<<endl;
        test=1;
        int c=3;
        for(int i=0; i<edge; i++)
        {
            string from,to;
            cin>>from>>to;
            if(mp1[from]==0)
            {
                mp1[from]=c;
                mp2[c]=from;
                c++;
            }
            if(mp1[to]==0)
            {
                mp1[to]=c;
                mp2[c]=to;
                c++;
            }
            g[mp1[from]].push_back(mp1[to]);
            g[mp1[to]].push_back(mp1[from]);
        }

        string src,dst;
        cin>>src>>dst;
        if(src==dst) cout<<src<<" "<<dst<<endl;
        else if(mp1[src]==0 || mp1[dst]==0) cout<<"No route"<<endl;
        else bfs(mp1[src],mp1[dst]);
        loop0(i,MAX) g[i].clear();
        mp1.clear();
        mp2.clear();
    }
    return 0;
}

UVa – 567 – Risk

Arunima Mandal Leave a comment 
#include <bits/stdc++.h>

#define ms(a,b)         memset(a,b,sizeof(a))
#define pb(a)           push_back(a)
#define db              double
#define ft              float
#define ll              long long
#define ull             unsigned long long
#define ff              first
#define ss              second
#define qu              queue
#define pqu             priority_queue
#define vc              vector
#define vi              vector<int>
#define vll             vector<long long>
#define pii             pair<int,int>
#define pis             pair<int,string>
#define psi             pair<string,int>
#define all(x)          x.begin(),x.end()
#define CIN            ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n)      for(int i=0;i<n;i++)
#define loop1(i,n)      for(int i=1;i<=n;i++)
#define stlloop0(i,x)   for(int i=0;i<x.size();i++)
#define stlloop1(x)     for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)       __gcd(a, b)
#define lcm(a, b)       ((a)*((b)/gcd(a,b)))
#define PI              3.14159265358979323846264338328
#define MAX             2004

using namespace std;

bool visited[MAX];
int dis[MAX];
vector<int> g[MAX];

int bfs(int src,int dst)
{
    ms(dis,0);
    dis[src]=0;
    ms(visited,0);
    visited[src]=1;

    qu<int> q;
    q.push(src);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(u==dst) return dis[dst];
        for(int i=0; i<g[u].size(); i++)
        {
            int v=g[u][i];
            if(!visited[v])
            {
                visited[v]=1;
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return -1;
}

int main()
{
    //CIN;
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int xxx,z=0;
    while(scanf("%d",&xxx)==1)
    {
        z++;
        loop0(i,xxx)
        {
            int xx;
            scanf("%d",&xx);
            g[1].pb(xx);
            g[xx].pb(1);
        }

        for(int i=2; i<=19; i++)
        {
            int x,to;
            scanf("%d",&x);
            loop0(j,x)
            {
                scanf("%d",&to);
                g[i].push_back(to);
                g[to].push_back(i);
            }
        }
        int n,src,dst;
        scanf("%d",&n);
        printf("Test Set #%d\n",z);
        loop0(i,n)
        {
            scanf("%d %d",&src,&dst);
            printf("%2d to %2d: %d\n",src,dst,bfs(src,dst));
        }
        printf("\n");
        loop0(i,MAX) g[i].clear();
    }
    return 0;
}

UVa – 336 – A node too far

Arunima Mandal Leave a comment

In UDebug of this problem,there are one or more wrong input cases for which this code will show wrong output, but actually those input cases are invalid for this problem !! So don’t bother with the UDebug output, this code will be Accepted in UVa OJ since this code is for all valid input !! 😀


#include <bits/stdc++.h>

#define ms(a,b)         memset(a,b,sizeof(a))
#define pb(a)           push_back(a)
#define db              double
#define ft              float
#define ll              long long
#define ull             unsigned long long
#define ff              first
#define ss              second
#define vc              vector
#define vi              vector<int>
#define vll             vector<long long>
#define pii             pair<int,int>
#define pis             pair<int,string>
#define psi             pair<string,int>
#define all(x)          x.begin(),x.end()
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n)       for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define stlloop(x)      for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)       __gcd(a, b)
#define lcm(a, b)       ((a)*((b)/gcd(a,b)))
#define PI              3.14159265358979323846264338328
#define MAX             2004

using namespace std;

bool visited[MAX];
int dis[MAX];
vc <int> g[MAX];
map<ll,int> mp;

int bfs(int src,ll ttl)
{
    int d=1;
    dis[src]=0;
    ms(visited,0);
    ms(dis,0);
    visited[src]=1;
    queue<int> Q;
    Q.push(src);
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(int i=0; i<g[u].size(); i++)
        {
            int v=g[u][i];
            if(!visited[v]  && dis[u]+1<=ttl)
            {
                dis[v]=dis[u]+1;
                d++;
                visited[v]=1;
                Q.push(v);
            }
        }
    }
    return d;
}

int main()
{
      CIN;
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int edge;
    for(int j=1;;)
    {
        cin>>edge;
        if(edge==0) break;
        int c=1;
        for(int i=0; i<edge; i++)
        {
            ll from,to;
            cin>>from>>to;
            if(mp[from]==0)
            {
                mp[from]=c;
                c++;
            }
            if(mp[to]==0)
            {
                mp[to]=c;
                c++;
            }
            g[mp[from]].push_back(mp[to]);
            g[mp[to]].push_back(mp[from]);
        }
        ll src,ttl;
        while(cin>>src>>ttl)
        {
            if(src==0 && ttl==0) break;
            int a=c-bfs(mp[src],ttl)-1;
            cout<<"Case "<<j<<": "<<a<<" nodes not reachable from node "<<src<<" with TTL = "<<ttl<<"."<<endl;
            j++;
        }
        loop0(i,MAX) g[i].clear();
        mp.clear();
    }
    return 0;
}