UVA 11710 - Expensive subway(cpp file)

Problem Type : Graph (Minimum Spanning Tree)



#include<bits/stdc++.h>
#define MAX 100000
using namespace std;
long par[MAX],n,m;
map<string ,long >mymap;
string n1,n2,n3;
struct node
{
    long node1;
    long node2;
    long cost;

};
node arr[MAX];
void make_set()
{
    long i;
    for(i=0; i<n; i++)
    {
        par[i]=i;
    }
}
long find_set(long n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n];
}
bool comp(node x,node y)
{
    return x.cost < y.cost;
}
int main()
{
    long i,j,k,l,node,x,y,c,ux,uy,px,cou,sum;
    while(scanf("%ld%ld",&n,&m)==2)
    {
        if(n==0 && m==0)
            break;
        getchar();
        for(i=0; i<n; i++)
        {
            cin >> n1;
            mymap[n1]=i;
        }
        for(i=0; i<m; i++)
        {
            cin>> n2 >>n3 >> c;
            x=mymap[n2];
            y=mymap[n3];
            arr[i].node1=x;
            arr[i].node2=y;
            arr[i].cost=c;
        }
        cin >> n1;
        x=mymap[n1];
        make_set();
        sort(arr,arr+m,comp);
        cou=0;
        sum=0;
        for(i=0; i<m; i++)
        {
            ux= find_set(arr[i].node1);
            uy= find_set(arr[i].node2);
            if(ux!=uy)
            {
                sum+=arr[i].cost;
                par[ux]=uy;
                cou++;

            }
            if(cou==n)
                break;
        }
        px= find_set(x);
        cou=0;
        for(i=0; i<n; i++)
        {
            if(i==x)
                continue;
            else
            {
                ux=find_set(i);
                if(ux!=px)
                {
                    cou=1;
                }

            }
        }
        if(cou==1)
            printf("Impossible\n");
        else
        {
            printf("%ld\n",sum);
        }
        mymap.clear();

    }

}

UVA 10034 - Freckles(cpp file)

Problem Type : Graph (Minimum Spanning Tree)


#include<stdio.h>
#include<math.h>
#include<algorithm>
#define MAX 5000
using namespace std;
int n,par[MAX];
struct node
{
    int n1;
    int n2;
    double cost;

};
node arr[MAX];
struct cor
{
    double px;
    double py;
};
cor arra[MAX];
bool comp(node x ,node y)
{
    return x.cost<y.cost;
}

void make_set()
{
    int i;
    for(i=0; i<n; i++)
    {
        par[i]=i;
    }
}
int find_set(int n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n];
}
int main()
{

    double mat[MAX],u,v,a,b,sum;
    int test,i,j,k,len,c,cas=0,ux,uy;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d",&n);
        for(i=0; i<n; i++)
        {
            scanf("%lf %lf",&arra[i].px,&arra[i].py);
        }
        make_set();
        c=0;
        for(i=0; i<n-1; i++)
        {
            for(j=i+1; j<n; j++)
            {
                a=pow((arra[i].px-arra[j].px),2);
                b=pow((arra[i].py-arra[j].py),2);
                arr[c].n1=i;
                arr[c].n2=j;
                arr[c].cost=sqrt(a+b);
                c++;
            }
        }
        sort(arr,arr+c,comp);
        int cnt=0;
        sum=0;
        for(i=0; i<c; i++)
        {
            ux=find_set(arr[i].n1);
            uy=find_set(arr[i].n2);
            if(ux!=uy)
            {
               par[ux]=uy;
                sum+=arr[i].cost;
                cnt++;
                if(cnt==n)
                    break;

            }

        }
        if(cas!=0)
            printf("\n");
        cas++;
        printf("%.2lf\n",sum);

    }

}

UVA 1174 - IP-TV(cpp file)

Problem Type :Graph( Minimum Spanning Tree)




#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<algorithm>
#define MAX 50002
using namespace std;
long int par[MAX],n,m,cou;
map<string,long int>mymap;
struct name
{
    long int node1;
    long int node2;
    long int cost;
};
name arr[MAX];
void make_set()
{
    long int i;
    for(i=0; i<n; i++)
    {
        par[i]=i;
    }

}
int find_set(long int n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n];
}
bool comp(name x,name y)
{
    return x.cost<y.cost;
}
long int  Union(long int x,long int y)
{
    long   int ux,uy;
    ux=find_set(x);
    uy=find_set(y);
    if(ux==uy)
    {
        return 0;
    }
    else
    {
        cou++;
        par[ux]=uy;
        return 1;
    }
}
int main()
{
    long  int test,i,j,c1,node,k,cou,sum,cas=0,ux,uy,x,y;
    string n1,n2;
    scanf("%ld",&test);
    getchar();
    getchar();
    while(test--)
    {
        node=0;
        i=0;
        scanf("%ld %ld",&n,&m);
        getchar();
        k=m ;
        for(n=0; n<m; n++)
        {
            cin >>n1>>n2>>c1;
            if(mymap.find(n1)==mymap.end())
            {
                mymap[n1]=node;
                node=node+1;
            }
            if(mymap.find(n2)==mymap.end())
            {
                mymap[n2]=node;
                node=node+1;
            }

            x =mymap[n1];
            y =mymap[n2];
            arr[n].node1=x;
            arr[n].node2=y;
            arr[n].cost=c1;
        }
        sort(arr,arr+m,comp);
        make_set();
        cou=0;
        sum=0;
        for(i=0; i<m; i++)
        {
            ux=arr[i].node1;
            uy=arr[i].node2;
            x=Union(ux,uy);
            if(x!=0)
            {
                sum+=arr[i].cost;
            }
            if(cou==n)
                break;
        }
        if(cas!=0)
            printf("\n");
        cas++;

        printf("%ld\n",sum);

        mymap.clear();
    }
    return 0;
}

UVA 11631 - Dark roads(cpp file)

Problem Type : Graph(Minimum Spanning Tree)



#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAX 200008
using namespace std;
long int par[MAX],v,e,cou;
struct node
{
    long  int node1;
    long int node2;
    long int cost;
};
node arr[MAX];
void make_set(long int n)
{
    long int i;
    for(i=0; i<n; i++)
    {
        par[i]=i;
    }
}
long int find_set(int n)
{
    if(par[n]!=n)
       par[n]=find_set(par[n]);
    return par[n];

}
bool comp(node x,node y)
{

        return x.cost<y.cost;

}
long int  Union(long int x,long int y)
{
  long   int ux,uy;
    ux=find_set(x);
    uy=find_set(y);
    if(ux==uy)
    {
        return 0;
    }
    else
    {
        cou++;
        par[ux]=uy;
        return 1;
    }
}

int main()
{

    long int i,j,k,ux,uy,sum,x,allcost;
    while(scanf("%ld %ld",&v,&e)&&v&&e)
    {
        make_set(v);
        allcost=0;
        for(i=0; i<e; i++)
        {
            scanf("%ld %ld %ld",&arr[i].node1,&arr[i].node2,&arr[i].cost);
            allcost+=arr[i].cost;

        }
        sort(arr,arr+e,comp);
        cou=0;
        sum=0;
        for(i=0; i<e; i++)
        {
            ux=arr[i].node1;
            uy=arr[i].node2;
            x=Union(ux,uy);
            if(x!=0)
            {
                sum+=arr[i].cost;
            }
            if(cou==v)
                break;
        }
        printf("%ld\n",allcost-sum);
    }



}

UVA 657 - The die is cast(cpp file)

Problem Type : Graph (DFS)





#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAX 51
using namespace std;
int X[4]= {-1,0,0,1};
int Y[4]= {0,-1,1,};
char mat[MAX][MAX];
int color[MAX][MAX],dot[MAX][MAX],n,m,cou=0;
void dfs1(int i,int j)
{
    dot[i][j]=1;
    int vx,vy,k;
    for(k=0; k<4; k++)
    {
        vx= i+X[k];
        vy =j+Y[k];
        if(vx>=0 && vx<n && vy>=0 && vy<m)
        {
            if(mat[vx][vy]=='X' && dot[vx][vy]==0)
            {
                dfs1(vx,vy);
            }
        }
    }
}
int dfs(int i,int j)
{
    if(mat[i][j]=='X'&& dot[i][j]==0)
    {
        dfs1(i,j);
        cou++;
    }
    color[i][j]=1;
    int vx,vy,k;
    for(k=0; k<4; k++)
    {
        vx=i+X[k];
        vy=j+Y[k];
        if(vx>=0 && vx<n && vy>=0 && vy<m && (mat[vx][vy]=='*'|| mat[vx][vy]=='X'))
        {
            if(color[vx][vy]==0)
            {
                dfs(vx,vy);
            }
        }
    }

    return cou;
}


int main()
{
    int i,j,k,arr[MAX],cas=0;
    while(scanf("%d %d",&m,&n)&&m&&n)
    {

        cas++;
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                scanf(" %c",&mat[i][j]);
            }
        }
        k=0;
        int sp=0;
        int l;
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                cou=0;
                if((mat[i][j]=='*' && color[i][j]==0)|| (mat[i][j]=='X' && color[i][j]==0))
                {
                    l=dfs(i,j);
                    arr[k++]=l;
                    sp=1;
                }
            }
        }
        sort(arr,arr+k);
        printf("Throw %d\n",cas);
        if(sp==1)
        {
            for(i=0; i<k-1; i++)
            {
                printf("%d ",arr[i]);
            }
            printf("%d",arr[k-1]);
        }
        else
        {
            printf("0");
        }
        printf("\n\n");
        memset(arr,0,sizeof(arr));
        memset(color,0,sizeof(color));
        memset(dot,0,sizeof(dot));
        memset(mat,'\0',sizeof(mat));
    }
}

UVA 12289 - One-Two-Three(c file)

Problem Type : String

#include<stdio.h>

#include<string.h>

int main()

{

    int i,j,n,len,one ,two;

    char ch[20];

    scanf("%d",&n);

    getchar();

    for(i=1; i<=n; i++)

    {

       gets(ch);

        len=strlen(ch);

        if(len==3)

        {

            one=0;

            two=0;

            for(j=0; j<len; j++)

            {

                if(ch[j]=='O'|| ch[j]=='o')

                    one++,two++;

                else if(ch[j]=='n'|| ch[j]=='N')

                     one++;

                else if(ch[j]=='E'|| ch[j]=='e')

                     one++;

                else if(ch[j]=='t'|| ch[j]=='T')

                     two++;

                else if(ch[j]=='w'|| ch[j]=='W')

                     two++;

            }

            if(one>two)

            {

                printf("1\n");

            }

            else

            {

                printf("2\n");

            }

        }

        else if(len==5)

        {

            printf("3\n");

        }

    }

    return 0;

}

UVA 11470 - Square Sums(cpp file)

Problem Type : Graph(NO ALGORITHM USE)






#include<stdio.h>
#include<string.h>
#define MAX 11
int mat[MAX][MAX],color[MAX][MAX];
int main()
{
    int n,i,j,sum ,cas=0,m;
    while(scanf("%d",&m)&&m)
    {
        cas++;
        n=m;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                scanf("%d",&mat[i][j]);
            }
        }
        printf("Case %d:",cas);
        sum =0;
        for(i=1; i<=n; i++)
        {
            sum=0;
            for(j=i; j<=n; j++)
            {
                if(color[j][n]==0)
                {
                    sum+=mat[j][n];
                    color[j][n]=1;
                }
                if(color[j][i]==0)
                {
                    sum+=mat[j][i];
                    color[j][i]=1;
                }
                if(color[i][j]==0)
                {
                    sum+= mat[i][j];
                    color[i][j]=1;
                }
                if(color[n][j]==0)
                {
                    sum+=mat[n][j];
                    color[n][j]=1;
                }
            }
            printf(" %d",sum);
            if(i==n)
                break;

            n--;
        }
        printf("\n");
        memset(color,0,sizeof(color));

    }

}

UVA 10583 - Ubiquitous Religions(cpp file)

Problem Type : Disjoint Set Data Structure





#include<stdio.h>
#include<string.h>
#define MAX 50000
using namespace std;
long int par[MAX],coun;
void make_set(long n)
{
    long i;
    for(i=1; i<=n; i++)
    {
        par[i]=i;
    }
}
long int find_set(long n)
{
    if(n!=par[n])
    {
        par[n]=find_set(par[n]);
    }
    return par[n];
}
void Union(long n,long m)
{
    int ux=find_set(n);
    int uy=find_set(m);
    if(ux==uy)
    {
        return;
    }
    else
    {
        coun--;
        par[ux]=uy;
    }
}
int main()
{
    long int n,m,i,j,k,node1,node2,cas=0;
    while(scanf("%ld%ld",&n,&m)&&n&&m)
    {
        cas++;
        coun=n;
        make_set(n);
        for(i=1;i<=m;i++)
        {
            scanf("%ld %ld",&node1,&node2);
            Union(node1,node2);
        }
        printf("Case %ld: %ld\n",cas,coun);
        memset(par,0,sizeof(par));

    }


}

UVA 459 - Graph Connectivity(cpp file)

Problem Type : Graph (Disjoint set)




#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAX 100
using namespace std;
int par[MAX];
int find_set(int n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n];
}
void make_set(int n)
{
    int i;
    for(i=1;i<=n;i++)
    {
        par[i]=i;
    }
}
void Union(int x,int y)
{
    int ux=find_set(x);
    int uy=find_set(y);
    if(ux==uy)
    {
        return;
    }
    else
    {
        par[ux]=uy;
    }
}
char arr[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
int main()
{
    int test,node,node1,node2,i,j,k,len,cas=0,arr1[MAX];
    char a,b,big,ch[2];
    scanf("%d",&test);
    getchar();
    getchar();
    while(test--)
    {
        if(cas!=0)
            printf("\n");
        cas++;
        scanf("%c",&big);
        getchar();
        for(i=0;i<26;i++)
        {
            if(arr[i]==big)
            {
                make_set(i+1);
                node=i+1;
                break;
            }
        }
        //printf("%d\n",node);
        while(gets(ch))
        {
            //printf("yes\n");
         if(strcmp(ch,"")==0)
            break;

            for(i=0;i<26;i++)
            {
                if(ch[0]==arr[i])
                {
                    node1=i+1;
                    break;
                }
            }
            for(i=0;i<26;i++)
            {
                if(ch[1]==arr[i])
                {
                    node2=i+1;
                    break;
                }
            }
            Union(node1,node2);

        }
        int x=0,coun=0;
        for(i=1;i<=node;i++)
        {
            arr1[x]=find_set(i);
            x++;
        }
        sort(arr1,arr1+node);
     k=1;
     for(i=0;i<node-1;i++)
     {
          if(arr1[i]==arr1[i+1])
          {
              continue;
          }
          else
          {
              k++;
          }
     }
     printf("%d\n",k);
     memset(par,0,sizeof(par));

    }



}

UVA 11561 - Getting Gold(cpp file)

Problem Type : Graph (BFS)




#include<cstdio>
#include<cstring>
#include<queue>
#define MAX 60
using namespace std;
int n,m,color[MAX][MAX],getgold=0,cou=0;
int X[4]= {-1,0,0,1};
int Y[4]= {0,-1,1,0};
char mat[MAX][MAX];
int bfs(int i,int j)
{
    if(mat[i-1][j]=='T')
    {
        return getgold;
    }
    else if(mat[i][j-1]=='T')
    {
        return getgold;
    }
    else if(mat[i][j+1]=='T')
    {
        return getgold;
    }
    else if(mat[i+1][j]=='T')
    {
        return getgold;
    }
    queue<int>Q;
    Q.push(i);
    Q.push(j);
    color[i][j]=1;
    int vx,vy,k,ux,uy;
    while(!Q.empty())
    {
        ux=Q.front();
        Q.pop();
        uy=Q.front();
        Q.pop();
        for(k=0; k<4; k++)
        {
            vx=ux+X[k];
            vy=uy+Y[k];
            if(vx>=1 && vx<=n && vy>=1 && vy<=m && mat[vx][vy]!='#')
            {

                if(color[vx][vy]==0)
                {
                    color[vx][vy]=1;
                    if(mat[vx][vy]=='G')
                    {
                        getgold++;
                    }
                    if(mat[vx-1][vy]=='T')
                    {
                        continue;
                    }
                    else if(mat[vx][vy-1]=='T')
                    {
                        continue;
                    }
                    else if(mat[vx][vy+1]=='T')
                    {
                        continue;
                    }
                    else if(mat[vx+1][vy]=='T')
                    {
                        continue;
                    }

                    Q.push(vx);
                    Q.push(vy);
                }

            }
        }
    }

    return getgold;
}
int main()
{
    int i,j,len,posi,posj;
    while(scanf("%d %d",&m,&n)==2)
    {
        getgold=0;
        getchar();
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=m; j++)
            {
                scanf(" %c",&mat[i][j]);
                if(mat[i][j]=='P')
                {
                    posi=i;
                    posj=j;
                }
            }
        }
        int k;
        cou=0;
        k= bfs(posi,posj);
        printf("%d\n",k);
        memset(color,0,sizeof(color));
        memset(mat,'\0',sizeof(mat));

    }
return 0;
}

UVA 11352 - Crazy King(cpp file)

Problem Type : Graph(BFS)




#include<stdio.h>
#include<string.h>
#include<queue>
#define MAX 101
using namespace std;
int n,m,color[MAX][MAX],cost[MAX][MAX];
int x[8]={-2,-2,-1,-1,1,1,2,2};
int y[8]={-1,1,-2,2,-2,2,-1,1};

int X[8]={-1,-1,-1,0,0,1,1,1};
int Y[8]={-1,0,1,-1,1,-1,0,1};
char mat[MAX][MAX];
void bfs(int i,int j)
{
    int vx,vy,ux,uy,k;
    queue<int>Q;
    color[i][j]=1;
    Q.push(i);
    Q.push(j);
    while(!Q.empty())
    {
         ux=Q.front();
         Q.pop();
         uy=Q.front();
         Q.pop();
         for(k=0;k<8;k++)
         {
             vx=ux+x[k];
             vy=uy+y[k];
             if(vx>=1 && vx<=n && vy>=1 && vy<=m && mat[vx][vy]=='.')
             {
                 if(color[vx][vy]==0)
                 {
                    color[vx][vy]=1;
                 }

             }
         }
    }
}
int bfs1(int i,int j)
{
    int vx,vy,ux,uy,k,cont=0;
    queue<int>Q;
    color[i][j]=1;
    Q.push(i);
    Q.push(j);
    cost[i][j]=0;

    while(!Q.empty())
    {
         ux=Q.front();
         Q.pop();
         uy=Q.front();
         Q.pop();
         for(k=0;k<8;k++)
         {
             vx=ux+X[k];
             vy=uy+Y[k];
             if(vx>=1 && vx<=n && vy>=1 && vy<=m && mat[vx][vy]=='.')
             {
                 if(color[vx][vy]==0)
                 {
                    color[vx][vy]=1;
                    cost[vx][vy]=cost[ux][uy]+1;
                    Q.push(vx);
                    Q.push(vy);
                 }

             }
             if(mat[vx][vy]=='B')
             {
                 cost[vx][vy]=cost[ux][uy]+1;
                return cost[vx][vy];
             }
         }

    }
    return 0;
}

int main()
{
    int test,i,j,k,len,kingi,kingj;
    scanf("%d",&test);
    getchar();
    while(test--)
    {
        scanf("%d %d",&n,&m);
        getchar();
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=m; j++)
            {
                scanf(" %c",&mat[i][j]);
                if(mat[i][j]=='A')
                {
                    kingi=i;
                    kingj=j;
                }
            }
        }

        memset(color,0,sizeof(color));

        for(i=1; i<=n; i++)
        {
            for(j=1; j<=m; j++)
            {
                if(mat[i][j]=='Z' && color[i][j]==0)
                {
                    bfs(i,j);
                }
            }

        }

        int sp;
        sp=bfs1(kingi,kingj);
        if(sp==0)
        {
            printf("King Peter, you can't go now!\n");
        }
        else
        {
            printf("Minimal possible length of a trip is %d\n",sp);
        }
        memset(mat,'\0',sizeof(mat));
        kingi=0;
        kingj=0;
    }
    return 0;

}

UVA 11094 - Continents(cpp file)

Problem Type : Graph (DFS)



#include<stdio.h>
#include<string.h>
#define MAX 21
char mat[MAX][MAX],c;
int X[4]={-1,0,0,1};
int Y[4]={0,-1,1,0};
int color[MAX][MAX],n,m,pn,pm,p;
int dfs(int i,int j)
{
    int vx,vy,k;
    if(color[i][j]==0)
    {
        color[i][j]=1;
        p++;
    }
    for(k=0; k<4; k++)
    {
        vx=i+X[k];
        vy=(j+Y[k])%n;

        if(vy<0)
            vy=n-1;

        if(mat[vx][vy]== c &&color[vx][vy]==0)
        {
            dfs(vx,vy);
        }
    }
    return p;
}
int main()
{

    int i,j,k,len,test=0,x;
    while(scanf("%d %d",&m,&n)==2)
    {

        getchar();
        for(i=0; i<m; i++)
        {
            for(j=0; j<n; j++)
            {
                scanf(" %c",&mat[i][j]);
            }
        }
        scanf("%d %d",&pm,&pn);
        c=mat[pm][pn];
        dfs(pm,pn);

        int k=0,b;
        for(i=0; i<m; i++)
        {
            for(j=0; j<n; j++)
            {
                p=0;
                if(mat[i][j]==c && color[i][j]==0)
                {
                   x=dfs(i,j);
                    if(k<x)
                    {
                        k=x;
                    }
                }
            }
        }

        printf("%d\n",k);
        memset(color,0,sizeof(color));
        memset(mat,'\0',sizeof(mat));
    }
}

UVA 10946 - You want what filled?(cpp file)

Problem Type : Graph (DFS)


#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#define MAX 55
#define MAX1 2508
using namespace std;
struct name
{
    int nm;
    char ch;
};
name R[MAX1];
int n,m,color[MAX][MAX];
int X[4]= {-1,0,0,1};
int Y[4]= {0,-1,1,0};
char mat[MAX][MAX],c,p;
bool comp(name x,name y)
{
    if(x.nm > y.nm)
    {
        return true;
    }
    else if(x.nm==y.nm && x.ch<y.ch)
    {
        return true;
    }
    return false;
}
int dfs(int i,int j)
{
    int vx,vy,k;
    if(color[i][j]==0)
    {
        mat[i][j]='.';
        color[i][j]=1;
        p++;
    }
    for(k=0; k<4; k++)
    {
        vx=i+X[k];
        vy=j+Y[k];
        if(mat[vx][vy]==c && vx>=0 && vx<n && vy>=0 && vy<m)
        {
            dfs(vx,vy);
        }
    }
    return p;
}
int main()
{
    int i,j,k,len,cas=0;
    while(scanf("%d %d",&n,&m)==2)
    {
        cas++;
        if(n==0 && m==0)
            break;
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                scanf(" %c",&mat[i][j]);
            }
        }
        k=0;
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                p=0;
                if(mat[i][j]!='.' && color[i][j]==0)
                {
                    c=mat[i][j];
                    int x=dfs(i,j);
                    R[k].ch=c;
                    R[k].nm=x;
                    k++;
                }
            }
        }

        sort(R,R+k,comp);
        printf("Problem %d:\n",cas);
        for(i=0; i<k; i++)
        {
            printf("%c ",R[i].ch);
            printf("%d\n",R[i].nm);
        }
        memset(color,0,sizeof(color));
        memset(mat,'\0',sizeof(mat));
    }
    return 0;
}

UVA 871 - Counting Cells in a Blob(cpp file)

Problem Type : Graph(DFS)


#include<stdio.h>
#include<string.h>
#define MAX 26
int X[8]= {-1,-1,-1,0,0,1,1,1};
int Y[8]= {-1,0,1,-1,1,-1,0,1};
char mat[MAX][MAX];
int color[MAX][MAX],m,n,p;
int dfs(int i,int j)
{
    int  vx,vy,k;
    if(color[i][j]==0)
    {
        p++;
        color[i][j]=1;
    }
    for(k=0; k<8; k++)
    {
        vx=i+X[k];
        vy=j+Y[k];
        if(vx>=0 && vx<m && vy>=0 && vy<=n && mat[vx][vy]=='1')
        {
            if(color[vx][vy]==0)
            {
                dfs(vx,vy);
            }
        }
    }
    return p;
}
int main()
{
    int i,j,len,test,c=0,k,arr[MAX];
    scanf("%d",&test);
    getchar();
    getchar();
    while(test--)
    {
        memset(mat,'\0',sizeof(mat));
        memset(color,0,sizeof(color));
        if(c!=0)
        {
            printf("\n");
        }
        c++;
        m=-1;
        while(gets(mat[++m]))
        {
            int l=strlen(mat[m]);
            if(l==0)
                break;
        }
        k=0;
        int x=0;
        for(i=0; i<m; i++)
        {
            n=strlen(mat[i]);
            for(j=0; j<n; j++)
            {
                p=0;
                if(mat[i][j]=='1' && color[i][j]==0)
                {
                    int q =dfs(i,j);
                    if(x<q)
                    {
                        x=q;
                    }
                }
            }
        }
        printf("%d\n",x);
    }
return 0;
}

UVA 785 - Grid Colouring(cpp file)

Problem Type : Graph(DFS)





#include<stdio.h>
#include<string.h>
#define MAX1 31
#define MAX 81
char mat[MAX1][MAX],c,contour;
int X[8]= {-1,0,0,1};
int Y[8]= {0,-1,1,0};
int color[MAX1][MAX];
void dfs(int i,int j)
{
    int vx,vy,k;

    if(color[i][j]==0)
    {
        mat[i][j]=c;
        color[i][j]=1;
    }

    for(k=0; k<8; k++)
    {
        vx=i+X[k];
        vy=j+Y[k];
        if(mat[vx][vy]==' ')
        {
            dfs(vx,vy);
        }
    }
}
int main()
{
    int i,j,k,len,m=-1;
    while(gets(mat[0]))
    {
        if(mat[0][0]=='_')
        {
            break;
        }
        m=0;
        while(gets(mat[++m]))
        {
            if(mat[m][0]=='_')
                break;
        }
        int cou =0;
        int cou1=0;

        for(i=0; i<m; i++)
        {
            len=strlen(mat[i]);
            for(j=0; j<len; j++)
            {
                if(mat[i][j]!=' ' && mat[i][j]!='_')
                {
                    contour=mat[i][j];
                    cou=1;
                }
                if(cou=1)
                    break;
            }
            if(cou=1)
                break;
        }
        for(i=0; i<m; i++)
        {
            len=strlen(mat[i]);
            for(j=0; j<len; j++)
            {
                if(mat[i][j]!=' ' && mat[i][j]!=contour && mat[i][j]!='_' && color[i][j]==0)
                {
                    c=mat[i][j];
                    dfs(i,j);
                }
            }
        }
        for(i=0; i<=m; i++)
        {
            printf("%s\n",mat[i]);
        }
        memset(color,'\0',sizeof(color));
    }
return 0;
}
/*
XXXXXXXXXXXXXXXXXXXX
X       X          X
X # #   XXXXXXXX / X
X              X   X
XXXXXXXXXXXXXXXXXXXX
_____________________________


  XXXXXXXXXXXX       XXXXXX
 X       #   XXX  XXX   X X
 X  XX         X  X     X X
X  X  X  XXXXXXX  XXXXXXX
X   XX   X
 X       X  XXXX  XXXXXXXX
  XX     XXXX  X  X  /   X
   X           X  X    / X
   XXXXXXXXXXXXX  XXXXXXXX
_____________________________
*/

UVA 784 - Maze Exploration(cpp file)

Problem Type : Graph(DFS)


#include<cstdio>
#include<cstring>
#define MAX 100
using namespace std;
char mat[MAX][MAX];
int X[8]= {-1,-1,-1,0,0,1,1,1};
int Y[8]= {-1,0,1,-1,1,-1,0,1};
int m;
void dfs(int i,int j)
{
    int vx,vy,k;
    mat[i][j]='#';
    for(k=0; k<8; k++)
    {
        vx=i+X[k];
        vy=j+Y[k];
        if(mat[vx][vy]==' ')
        {
            dfs(vx,vy);
        }
    }
}
int main()
{

    int test,i,k,j,n,bound,cou;


    scanf("%d",&test);
    getchar();
    while(test--)
    {
        m=-1;
        while(gets(mat[++m]))
            if(mat[m][0]=='_')
                break;
        cou =0;
        for(i=0; i<m; i++)
        {
            int len = strlen(mat[i]);
            for(j=0; j<len; j++)
            {
                if(mat[i][j]=='*')
                {
                    dfs(i,j);
                    cou=1;
                }
                if(cou==1)
                    break;
            }
            if(cou==1)
                break;
        }
        for(i=0; i<=m; i++)
        {
           printf("%s\n",mat[i]);
        }

    }

}
/*
Sample input :
3
XXXXXXXXXXXXXXXXXXXXX
X   X   X   X   X   X
X           X   X   X
X   X   X   X   X   X
XXXXXX XXX XXXXXXXXXX
X   X   X   X   X   X
X   X     *         X
X   X   X   X   X   X
XXXXXXXXXXXXXXXXXXXXX
_________
XXXXXXXXX
X   X   X
X   *   X
X   X   X
XXXXXXXXX
X   X
X   X
X   X
XXXXX
_____
XXXXX
X   X
X * X
X   x
XXXXX
_____
*/

UVA 10008 - What's Cryptanalysis?(cpp file)

Problem Type : String



#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<algorithm>
using namespace std;
struct  name
{
    char ch;
    int r;
};
name R[26];
bool comp(name x,name y)
{
    if(x.r > y.r)
    {
        return true;
    }
    else if(x.r==y.r && x.ch<y.ch)
    {
        return true;
    }
    return false;
}
int main()
{
    int i,j,k,len,test;
    char des[1000];
    scanf("%d",&test);
    for(i=0; i<26; i++)
    {
        R[i].r=0;
    }
    getchar();
    while(test--)
    {
        gets(des);
        len = strlen(des);
        for(i=0; i<len; i++)
        {
            char c =toupper(des[i]);
            if(isalpha(c))
            {
                R[c-65].r++;
                R[c-65].ch = c;
            }
        }
    }
      sort(R,R+26,comp);
    for(i=0; R[i].r; i++)
    {
        printf("%c %d\n",R[i].ch,R[i].r);
    }

}

UVA 10336 - Rank the Languages(cpp file)

Problem Type : Graph(DFS)




#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define M 1000
using namespace std;
int X[4]= {-1,0,0,1};
int Y[4]= {0,-1,1,0};
char graph[M][M];
struct Hole
{
    char ch;
    int dep;
};

int n,H,W;
struct Rank
{
    char ch;
    int r;
};
struct Rank R[26];

void DFS(int x,int y)
{
    int tx,ty,i;
    char ch = graph[x][y];
    graph[x][y] = '*';

    for(i=0; i<8; i++)
    {
        tx = x + X[i];
        ty = y + Y[i];

        if(tx>=0&&tx<H&&ty>=0&&ty<W&&graph[tx][ty]==ch)
            DFS(tx,ty);
    }
}
bool comp(Rank x,Rank y)
{
    if(x.r > y.r)
    {
        return true;
    }
    else if(x.r==y.r && x.ch<y.ch)
    {
        return true;
    }
    return false;
}

int main()
{
    int t,i,j,k;
    scanf("%d",&t);

    for(k=1; k<=t; k++)
    {
        scanf("%d%d\n",&H,&W);
        for(i=0; i<H; i++)
        {
            for(j=0; j<W; j++)
            {
                scanf(" %c",&graph[i][j]);
            }
        }

        for(i=0; i<H; i++)
        {
            for(j=0; j<W; j++)
            {
                if(graph[i][j]!='*')
                {
                    R[graph[i][j]-97].r++;
                    R[graph[i][j]-97].ch = graph[i][j];
                    DFS(i,j);
                }
            }
        }
        sort(R,R+26,comp);

        printf("World #%d\n",k);
        for(i=0; R[i].r; i++)
        {
            printf("%c: %d\n",R[i].ch,R[i].r);
        }
        for(i=0; i<26; i++)
        {
            R[i].r=0;
            R[i].ch='\0';
        }
    }
    return 0;
}

UVA 11734 - Big Number of Teams will Solve This(cpp fie)

Problem Type : Ad hoc




#include<stdio.h>
#include<ctype.h>
#include<string.h>
#define MAX 1000
int main()
{
    char ch[MAX],des[MAX],ch1[MAX],des1[MAX];
    int i,j,len1,len2,test,cas=0,k,p;
    scanf("%d",&test);
    getchar();
    while(test--)
    {
        cas++;
        memset(ch,'\0',sizeof(ch));
        gets(ch);
        gets(des);
        len1=strlen(ch);

        len2=strlen(des);

        if(strcmp(ch,des)==0)
        {
            printf("Case %d: Yes\n",cas);
        }
        else
        {
            k=0;

           for(i=0; i<len1; i++)
            {
                if(isalpha(ch[i])||isdigit(ch[i]))
                {
                    ch1[k]=ch[i];
                    k++;
                }
            }
            ch1[k]='\0';

            p=0;
            for(i=0; i<len2; i++)
            {
                if(des[i]>='A'&&des[i]<='Z'||des[i]>='a'&&des[i]<='z' || des[i]>='0' &&des[i]<='9')
                {
                    des1[p]=des[i];
                    p++;
                }
            }
            des1[p]='\0';
            if(strcmp(ch1,des1)==0)
            {
                printf("Case %d: Output Format Error\n",cas);
            }
            else
            {
                printf("Case %d: Wrong Answer\n",cas);
            }


        }
    }


}

UVA 11244 - Counting Stars(cpp file)

Problem Type : Graph (BFS)



#include<stdio.h>
#include<cstring>
#include<queue>
#define size1 250

using namespace std;
int X[8]= {-1,-1,-1,0,0,1,1,1};
int Y[8]= {-1,0,1,-1,1,-1,0,1};
char mat[size1][size1];
int color[size1][size1],n,m;
int  bfs(int i,int j)
{
    int ux,uy,vx,vy,k;
    queue<int>Q;
    color[i][j]=1;
    Q.push(i);
    Q.push(j);
    int p=0,q=0;
    while(!Q.empty())
    {
        ux=Q.front();
        Q.pop();
        uy=Q.front();
        Q.pop();
        for(k=0;k<8;k++)
        {
            vx=ux+X[k];
            vy=uy+Y[k];
            if(vx>=1 && vx<=n && vy>=1 && vy<=m && mat[vx][vy]=='*')
            {
                if(color[vx][vy]==0)
                {
                    color[vx][vy]=1;
                    q++;
                    Q.push(vx);
                    Q.push(vy);
                }
            }
        }
    }
    if(q==0)
    {
        p++;
    }
    return p;

}
int main()
{
    int i,j ,cou;
    while(scanf("%d %d",&n,&m)&&n&&m)
    {
        getchar();
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=m; j++)
            {
                scanf(" %c",&mat[i][j]);
            }
        }
        cou=0;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=m; j++)
            {
                if(mat[i][j]=='*'&&color[i][j]==0)
                {
                    cou +=bfs(i,j);
                }
            }
        }
        printf("%d\n",cou);
        memset(color,0,sizeof(color));
        memset(mat,'\0',sizeof(mat));

    }


}

UVA 10338 - Mischievous Children(cpp file)

Problem Type : Number Theory





#include<stdio.h>
#include<string.h>
#include<algorithm>
#define max 100
using namespace std;

unsigned long long  fact(unsigned long long  n)
{
    unsigned long long i,ren=1;
    for( i=1; i<=n; i++)
    {
        ren*=i;
    }
    return ren;
}
int main()
{
    char ch[max];
    unsigned long long int test,i,j,len,cou,k=0,store[max];
    unsigned long long int sum,ans,sum1,m;
    scanf("%llu",&test);
    getchar();
    while(test--)
    {

        k++;
        scanf("%s",&ch);
        len=strlen(ch);
        sort(ch,ch+len);
       // printf("%s\n",ch);
        m=1;
        for(i=0; i<len; i++)
        {
            cou=1;
            for(j=i+1;j<len; j++)
            {
                if(ch[i]==ch[j])
                {
                    cou++;
                }
                else
                    break;

            }
            if(cou!=1)
            {
                store[m]=cou;
                m++;
                i=j-1;
            }

        }
        sum=1;
        for(i=1; i<=len; i++)
        {
            sum*=i;
        }
        ans=1;
        for(i=1; i<m; i++)
        {
          ans = ans * fact(store[i]);
        }
        sum1=sum/ans;
        printf("Data set %llu: %llu\n",k,sum1);
        memset(ch,'\0',sizeof(ch));
    }




}

UVA 10929 - You can say 11(cpp file)

Problem Type : Number Theory



#include<stdio.h>
#include<string.h>
#define LEN 1110

int main()
{
  long long int i,j,len,k,cou,sum,m;
    char ch[LEN];
    while(scanf("%s",&ch)&&ch)
    {
        if(strcmp(ch,"0")==0)
            break;
        len = strlen(ch);
        sum=0;
        m=0;

        for(i=0; i<len; i++)
        {
            sum = m*10 + ch[i]-48;

            m = sum%11;
        }
        if(m==0)
        {

             printf("%s is a multiple of 11.\n",ch);
        }
        else
        {
           printf("%s is not a multiple of 11.\n",ch);
        }

    }
    return 0;
}

UVA 10922 - 2 the 9s(cpp file)

Problem Type : Ad hoc


#include<stdio.h>
#include<string.h>
#define LEN 1100
int count =0;
int check(long long n)
{
    int i;
    if(n==9)
    {
        count++;
        return count;
    }
    long int sum=0;
    for(i=0; ;i++)
    {
         sum+=n%10;
         n=n/10;
         if(n==0)
         {
             count++;
             break;
         }
    }
    //printf("%ld\n",sum);
    return check(sum);
}
int main()
{
  long long int i,j,len,k,cou,sum,m;
    char ch[LEN];
    while(scanf("%s",&ch)&&ch)
    {
        if(strcmp(ch,"0")==0)
            break;
        len = strlen(ch);
        sum=0;
        m=0;
        k=0;
        for(i=0; i<len; i++)
        {
            sum = m*10 + ch[i]-48;
            k+=ch[i]-48;
            m = sum%9;
        }
        if(m==0)
        {
           int   dept = check(k);
             printf("%s is a multiple of 9 and has 9-degree %d.\n",ch,dept);
        }
        else
        {
         printf("%s is not a multiple of 9.\n",ch);
        }
count=0;

    }
    return 0;
}

UVA 260 - Il Gioco dell'X(cpp file)

Problem Type : GRAPH(BFS)




#include<stdio.h>
#include<string.h>
#include<queue>
#define MAX 1111
using namespace std;
int color[MAX][MAX],n;
char mat[MAX][MAX];
int X[6]= {-1,-1,0,0,1,1};
int Y[6]= {-1,0,-1,1,0,1};
void bfs(int i,int j)
{
    int vx,ux,vy,uy,k;
    queue<int>Q;
    Q.push(i);
    Q.push(j);
    color[i][j]=1;
    while(!Q.empty())
    {
        ux=Q.front();
        Q.pop();
        uy = Q.front();
        Q.pop();
        for(k=0; k<6; k++)
        {
            vx = ux+X[k];
            vy = uy+Y[k];
            if((vx>=1&&vx<=n) && (vy>=1&&vy<=n) && mat[vx][vy]=='w')
            {
                if(!color[vx][vy])
                {
                    color[vx][vy]=1 ;
                    Q.push(vx);
                    Q.push(vy);
                }
            }
        }
    }
}
int main()
{
    int i ,j,l,cas=0;
    while(scanf("%d",&n)&&n)
    {
        cas++;
        getchar();
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                scanf(" %c",&mat[i][j]);
            }
        }

        for(i=1; i<=n; i++)
        {
            if(mat[i][1] == 'w' && color[i][1]==0)
            {
                bfs(i,1);
            }

        }
        int cou =0;
        for(i=1; i<=n; i++)
        {
            if(color[i][n]==1)
            {
                cou=1;
                break;
            }
        }
        if(cou==1)
            printf("%d W\n",cas);
        else if(cou ==0)
        {
            printf("%d B\n",cas);
        }

        memset(color,0,sizeof(color));
        memset(mat,'\0',sizeof(mat));
    }

}

UVA 12243 - Flowers Flourish from France(cpp file)

Problem Type : String



#include<stdio.h>
#include<string.h>
#include<ctype.h>
#define MAX 5000

int main()
{

    int i,j,k,len,cou;
    char ch[MAX],des[MAX];
    while(gets(ch))
    {
        if(strcmp(ch,"*")==0)
            break;
        len=strlen(ch);
        k=0;
       // printf("%s",ch);
        for(i=0; i<len; i++)
        {

            if(i==0)
            {
                des[k]=ch[i];
                //printf("%c\n",des[k]);
                k++;
            }
            else if(isalpha(ch[i]) && ch[i-1]==' ')
            {
               des[k]=ch[i];
               //printf("%c\n",des[k]);
               k++;
            }

        }
        des[k]='\0';

        //printf("%s",des);
        len = strlen(des);
        cou=0;
        for(i=0;i<len-1;i++)
        {
           char n= toupper(des[i]);
           char m= toupper(des[i+1]);
            if(m==n)
            {
                 continue;
            }
            else
            {
                cou=1;
                printf("N\n");
                break;
            }
        }
        if(cou==0)
        {
            printf("Y\n");
        }
        memset(ch,'\0',sizeof(ch));
    }
}

UVA 10009 - All Roads Lead Where?(cpp file)

Problem Type : GRAPH(BFS)


#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#include<vector>
#define MAX 10000
using namespace std;
map<string,char>mymap;
map<char,int>color;
map<char,char>par;
vector<char>vcc[MAX],v;

void bfs(char start)
{
    int i;
    char u;
    queue<char>Q;
    Q.push(start);
    color[start]=1;
    par[start]=start;
    while(!Q.empty())
    {
        u=Q.front();

        Q.pop();
        int len=vcc[u].size();
        for(i=0; i<len; i++)
        {
            if(color[vcc[u][i]]!=1)
            {
                //printf("%c\n",vcc[u][i]);
                color[vcc[u][i]]=1;
                Q.push(vcc[u][i]);
                par[vcc[u][i]]=u;
            }
        }
    }
    return;
}
int main()
{
    int test,i,j,k,cas=0, n,m;
    string node1,node2;
    char c;
    scanf("%d",&test);

    while(test--)
    {
        if(cas!=0)
            printf("\n");
        cas++;
        scanf("%d %d",&n,&m);
        getchar();
        for(i=0;i<9999;i++)
        {
            vcc[i].clear();
        }
        while(n--)
        {

            cin >> node1 >> node2;
            if(mymap.find(node1)==mymap.end())
            {
                c=node1[0];
                mymap[node1]=c;
            }
            if(mymap.find(node2)==mymap.end())
            {
                c=node2[0];
                mymap[node2]=c;
            }
            char kp=mymap[node1];
            char pk=mymap[node2];
            vcc[kp].push_back(pk);
            vcc[pk].push_back(kp);

        }
        while(m--)
        {
            cin >> node1 >> node2;
            char start = mymap[node1];
            char des = mymap[node2];
            par.clear();
            color.clear();
            bfs(start);
            v.push_back(des);
            for(i=0; ; i++)
            {
                v.push_back(par[des]);
                //printf("%c",par[des]);
                if(par[des]==start)
                    break;
                des=par[des];
            }
          for(i=v.size()-1; i>=0; i--)
            {
                printf("%c",v[i]);
            }
            printf("\n");
            v.clear();
        }

    }

    return 0;
}

UVA 336 - A Node Too Far(cpp file)

Problem Type : Graph(BFS)


#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<vector>
#define MAX 99900
using namespace std;
vector<long>vcc[MAX];
map<long,long>mymap;

long int color[MAX],cost[MAX] ,node,start,cost1,visited[MAX],cas=0,dif[MAX];
void bfs(long int start,long int c)
{
    cas++;
    // printf("%ld\n",c);
    long int i,j,u;
    color[start]=1;
    cost[start]=0;
    queue<long int>Q;
    long int  num=0;
    Q.push(start);
    while(!Q.empty())
    {
        u=Q.front();
        Q.pop();
        long int len = vcc[u].size();
        for(i=0; i<len; i++)
        {
            if(color[vcc[u][i]]!=1)
            {
                cost[vcc[u][i]]=cost[u]+1;
                if(cost[vcc[u][i]]>c)
                {
                    break;
                }
                num++;
                Q.push(vcc[u][i]);
                color[vcc[u][i]]=1;
            }
        }
    }
    printf("Case %ld: %ld nodes not reachable from node %ld with TTL = %ld.\n",cas,(node-num-1),start,c);

}
int main()
{
    long int i,j,k,l,n,m,t;
    while(scanf("%ld",&t)==1)
    {
        if(t==0)
        {
            break;
        }
        node=0;
        for(i=0; i<MAX; i++)
        {
            vcc[i].clear();
        }
        for(i=1; i<=t; i++)
        {
            scanf("%ld %ld",&n,&m);


            if(dif[n]!=1)
            {
                dif[n]=1;
                node=node+1;
            }
            if(dif[m]!=1)
            {
                dif[m]=1;
                node=node+1;;
            }
            vcc[n].push_back(m);
            vcc[m].push_back(n);

        }

        while(scanf("%ld %ld",&start,&cost1)==2)
        {
            if(start==0 && cost1==0)
            {
                break;
            }
            else
            {
                memset(cost,0,sizeof(cost));
                memset(color,0,sizeof(color));
                bfs(start,cost1);
            }



        }

        memset(dif,0,sizeof(dif));


    }

}