UVA 1112 - Mice and Maze(cpp file)

Problem Type :Dijkstra


#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
#define MAX 101
#define  INF 52312424
using namespace std;
int vertex,edge,source,ext,dist[MAX],cost[MAX][MAX];
vector<int>mat[MAX];
struct node
{
    int x,c;
    node(int d, int f)
    {
        x=d;
        c=f;
    }
    bool operator<(const node &p)const
    {
        return c>p.c;
    }
};
void djkstra(int s)
{
    int ux,i,j,vx;
    priority_queue<node>Q;
    dist[s]=0;
    Q.push(node(s,dist[s]));
    while(!Q.empty())
    {
        node top = Q.top();
        int ux = top.x;
        Q.pop();
        for(i=0; i<mat[ux].size(); i++)
        {
            vx= mat[ux][i];
            if(dist[vx]>dist[ux]+cost[ux][vx])
            {
                dist[vx]=dist[ux]+cost[ux][vx];
                Q.push(node(vx,dist[vx]));
            }
        }
    }

}
int main()
{
    int test,i,j,cas=0,m,n,c;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d %d %d %d",&vertex,&ext,&source,&edge);
        for(i=1; i<=edge; i++)
        {
            scanf("%d %d %d",&n,&m,&c);
            mat[m].push_back(n);
            cost[m][n]=c;
        }
        for(i=1; i<=vertex; i++)
        {
            dist[i]=INF;
        }
        djkstra(ext);
        int cou=0;
        for(i=1; i<=vertex; i++)
        {
            if(dist[i]<=source)
                cou++;
        }
        printf("%d\n",cou);
        if (test)
        {
            puts("");
        }
        for(i=0; i<=MAX; i++)
        {
            mat[i].clear();
        }
        memset(cost,0,sizeof cost);
    }

}

UVA 10986 - Sending email(cpp file)

Problem Type : Dijkstra



#include<bits/stdc++.h>
#define MAX 20001
#define INF 100000
using namespace std;
long int vertex,edge,source,des;
long int dist[MAX];
vector<long int>vcc[MAX],cost[MAX];
struct node
{
    long int x,c;
    node(long int d,long int f)
    {
        x=d;
        c=f;
    }
    bool operator<(const node &p)const
    {
        return c>p.c;
    }
};

void djkstra(long int s)
{
    priority_queue<node>Q;
    long  int ux,uy,vx,vy,i,j;
    dist[s]=0;
    Q.push(node(s,dist[s]));
    while(!Q.empty())
    {
        node top = Q.top();
        Q.pop();
        ux = top.x;
        for(i=0; i<vcc[ux].size(); i++)
        {
            long vx= vcc[ux][i];
            if(dist[vx]> dist[ux]+cost[ux][i])
            {
                dist[vx]=dist[ux]+cost[ux][i];
                Q.push(node(vx,dist[vx]));
            }

        }
    }
}
int main()
{
    long  int i,j,test,n,m,c,cas=0;
    scanf("%ld",&test);
    while(test--)
    {
        cas++;
        scanf("%ld %ld %ld %ld",&vertex,&edge,&source,&des);

        for(i=0; i<edge; i++)
        {
            scanf("%ld %ld %ld",&n,&m,&c);
            vcc[n].push_back(m);
            vcc[m].push_back(n);
            cost[m].push_back(c);
            cost[n].push_back(c);

        }
        for(i=0; i<vertex; i++)
        {
            dist[i]=INF;
        }
        djkstra(source);
        if(dist[des]==INF)
        {
            printf("Case #%ld: unreachable\n",cas);
        }
        else
        {
            printf("Case #%ld: %ld\n",cas,dist[des]);
        }
        for(i=0; i<MAX; i++)
        {
            vcc[i].clear();
        }
         for(i=0; i<MAX; i++)
        {
            cost[i].clear();
        }
    }

}

UVA 1207 - AGTC(cpp file)

Problem Type : DP (Levenshtein Distance)


#include<stdio.h>
#include<algorithm>
#include<string.h>
#define MAX 1502
using namespace std;
int arr[MAX][MAX],len1,len2;
void labistine(char s[],char des[],int len1,int len2)
{
    int i,j;
    for(i=1;i<len1;i++)
    {
        for(j=1;j<len2;j++)
        {
           if(s[i]==des[j])
           {
               arr[i][j]=arr[i-1][j-1];
           }
           else if(s[i]!=des[j])
           {
              int p=min(arr[i-1][j]+1,arr[i][j-1]+1);
              arr[i][j]=min(arr[i-1][j-1]+1,p);
           }
        }
    }
}
void init()
{
    int i,j;

        for(j=0;j<len2;j++)
        {
            arr[0][j]=j;
        }
        for(i=0;i<len1;i++)
        {
            arr[i][0]=i;
        }

}
int main()
{
    int i,j;
    char source[MAX],des[MAX];
    while(scanf("%d ",&len1)==1)
    {
        source[0]='a';
        for(i=1; i<=len1; i++)
        {
            scanf("%c",&source[i]);
        }
        len1+=1;
        source[len1]='\0';
        des[0]='a';
        scanf("%d ",&len2);
        for(i=1; i<=len2; i++)
        {
            scanf("%c",&des[i]);
        }
        len2+=1;
        des[len2]='\0';
        init();
        labistine(source,des,len1,len2);
        printf("%d\n",arr[len1-1][len2-1]);
        memset(arr,0,sizeof(arr));
    }
}

UVA 11349 - Symmetric Matrix

Problem Type : Matrix


#include<stdio.h>
#include<string.h>
#define MAX 105
long long int mat [MAX][MAX];
int main()
{
    char c;
  long  int n,i,j,tag,cas=0,test;
    scanf("%d",&test);

    while(test--)
    {
        getchar();
        scanf("N = %d",&n);
        cas++;
        tag=0;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                scanf("%lld",&mat[i][j]);
                if(mat[i][j]<0)
                {
                    tag=1;
                }
            }
        }
          int x,k;
        if(tag==0)
        {
            if(n%2==1)
            {
                 k=0;
                for(i=1; i<=n/2+1; i++)
                {
                    x=0;
                    for(j=1; j<=n; j++)
                    {
                        if(mat[j][i]==mat[n-x][n-k])
                        {
                            x++;
                            continue ;
                        }
                        else if(mat[j][i]!=mat[n-x][n-k])
                        {
                            x++;
                            tag=1;
                        }

                    }
                    k++;
                    if(tag==1)
                        break;
                }
            }
            else
            {
                int k=0;
                for(i=1; i<=n/2; i++)
                {
                  int  m=0;
                    for(j=1; j<=n; j++)
                    {

                        if(mat[j][i]==mat[n-m][n-k])
                        {
                                m++;
                            continue ;
                        }
                        else{

                            tag=1;
                        }

                    }
                    k++;
                    if(tag==1)
                        break;
                }
            }
        }
       if(tag==0)
       {
           printf("Test #%d: Symmetric.\n",cas);
       }
       else
       {
           printf("Test #%d: Non-symmetric.\n",cas);
       }

       memset(mat,0,sizeof(mat));
    }
}

UVA 12802 - Gift From the Gods(cpp file)

Problem Type : Ad hoc


#include<stdio.h>
#include<string.h>
struct p
{
    int n;
};
p arr[200];
int main()
{
    int test,i,j,x,cas=0,coun,k,len;
    char ch[111];
    while(scanf("%d",&test)==1)
    {
        getchar();
        cas++;
        coun=0;
        for(i=1; i<=test; i++)
        {
            scanf("%s",&ch);
            len= strlen(ch);
            int cou=0;
            for(j=97; j<=122; j++)
            {
                arr[j].n=0;
            }
            for(j=0; j<len-1; j++)
            {
                if(ch[j]==ch[j+1])
                {
                    cou=1;
                }
                else
                {
                    cou=0;
                    break;
                }
            }
            if(len==1)
            {
                cou=1;
            }
            for(j=0; j<len; j++)
            {
                x=ch[j];
                arr[x].n++;

            }
            if(len>1 && cou==0)
            {
                for(j=97; j<122; j++)
                {
                    for(k=j+1; k<=122; k++)
                    {
                        if(arr[j].n!=0 || arr[j].n!=0)
                        {
                            if(arr[j].n==arr[k].n)
                            {
                                cou=1;
                                break;
                            }
                        }
                    }
                    if(cou==1)
                    {
                        break;
                    }
                }
            }
            if(cou==0)
            {
                coun++;
            }

        }
        printf("Case %d: %d\n",cas,coun);
    }
}

UVA 12820 - Cool Word(cpp file)

Problem Type : String


#include<stdio.h>
#include<string.h>
struct p
{
    int n;
};
p arr[200];
int main()
{
    int test,i,j,x,cas=0,coun,k,len;
    char ch[111];
    while(scanf("%d",&test)==1)
    {
        getchar();
        cas++;
        coun=0;
        for(i=1; i<=test; i++)
        {
            scanf("%s",&ch);
            len= strlen(ch);
            int cou=0;
            for(j=97; j<=122; j++)
            {
                arr[j].n=0;
            }
            for(j=0; j<len-1; j++)
            {
                if(ch[j]==ch[j+1])
                {
                    cou=1;
                }
                else
                {
                    cou=0;
                    break;
                }
            }
            if(len==1)
            {
                cou=1;
            }
            for(j=0; j<len; j++)
            {
                x=ch[j];
                arr[x].n++;

            }
            if(len>1 && cou==0)
            {
                for(j=97; j<122; j++)
                {
                    for(k=j+1; k<=122; k++)
                    {
                        if(arr[j].n!=0 || arr[j].n!=0)
                        {
                            if(arr[j].n==arr[k].n)
                            {
                                cou=1;
                                break;
                            }
                        }
                    }
                    if(cou==1)
                    {
                        break;
                    }
                }
            }
            if(cou==0)
            {
                coun++;
            }

        }
        printf("Case %d: %d\n",cas,coun);
    }
}

UVA 10420 - List of Conquests(cpp file)

 Problem Type : Ad hoc


#include<iostream>
#include<string>
#include<string.h>
#include<cstdio>
#include<algorithm>
using namespace std;
struct mymap
{
    string p;
    int m;
};
mymap arr[2001];
bool comp(mymap n ,mymap x)
{
    return(n.p < x.p);
}
int main()
{
    int n,i,j,k,y,cou;
    string s1;
    char s[79],des[76];
    scanf("%d",&n);
    getchar();
    y=0;
    for(j=0; j<n; j++)
    {
        gets(s);
        k=0;
        for(i=0; i<strlen(s); i++)
        {

            if((s[i]>='A' && s[i]<='Z')&&!(s[i+1]>=65 && s[i+1]<=90)&&!(s[i+1]>=97 && s[i+1]<=122))
            {
                des[k]=s[i];
                k++;
                break;
            }
            else if ((s[i]>=97 &&s[i]<=122)&&!(s[i+1]>=97 && s[i+1]<=122)&&!(s[i+1]>=65 && s[i+1]<=90))
            {
                des[k]=s[i];
                k++;
                break;
            }
            else if(s[i]>=65 && s[i]<=90  || s[i]>=97 && s[i]<=122)
            {
                des[k]=s[i];
                k++;
            }
        }
        des[k]='\0';
        s1=(string)(des);
        cou=0;
        for(i=0; i<j; i++)
        {
            if(arr[i].p.compare(s1)==0)
            {
                cou=1;
                arr[i].m++;
            }
        }
        if(cou==0)
        {
            arr[y].p=s1;
            arr[y].m=1;
            cou=0;
            y++;
        }
    }
    sort(arr,arr+y,comp);
    for(i=0; i<y; i++)
    {
        cout << arr[i].p<<' '<<arr[i].m <<endl;
    }
    y=0;
    for(i=0; i<y; i++)
    {
        arr[i].m=0;
    }
    for(i=0; i<y; i++)
    {
        arr[i].p= '\0';
    }

}

UVA 11624 - Fire!(cpp file)

Problem Type : BFS(Harder)

#include<stdio.h>
#include<string.h>
#include<queue>
#define MAX 1003
using namespace std;
int X[]= {0,0,1,-1};
int Y[]= {1,-1,0,0};
int node,edge ,ux,uy,vx,vy;
char mat[MAX][MAX];
queue<int>fire,joy;
bool broke,cross;
bool boundary()
{
    if(vx>=0  && vx<node && vy>=0 && vy<edge)
        return true;
    else
        return false;
}
void bfsf()
{
    int num = fire.size();
    int i;
    num/=2;
    if(num==0)
    {
        return;
    }
    while(num--)
    {
        ux = fire.front();
        fire.pop();
        uy =  fire.front();
        fire.pop();
        for(i=0; i<4; i++)
        {
            vx=ux+X[i];
            vy=uy+Y[i];
            if(boundary()&& mat[vx][vy]=='.')
            {
                mat[vx][vy]='F';
                fire.push(vx);
                fire.push(vy);
            }
        }
    }
}
void bfsj()
{
    int num = joy.size();
    int i;
    num/=2;
    if(num==0)
    {
        broke = false;
        return;
    }
    while(num--)
    {
        ux = joy.front();
        joy.pop();
        uy = joy.front();
        joy.pop();
        for(i=0;i<4;i++)
        {
            vx= ux+X[i];
            vy= uy +Y[i];
            if(!boundary())
            {
               cross = false ;
               return;
            }
            if(boundary()&& mat[vx][vy]=='.')
            {
                mat[vx][vy]='J';
                joy.push(vx);
                joy.push(vy);
            }
        }
    }
}
int main()
{
    int test,i,j,k;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d %d",&node,&edge);
        getchar();
        while(!fire.empty())
        {
            fire.pop();
        }
        while(!joy.empty())
        {
            joy.pop();
        }
        for(i=0; i<node; i++)
        {
            for(j=0; j<edge; j++)
            {
                scanf(" %c",&mat[i][j]);
                if(mat[i][j]=='F')
                {
                    fire.push(i);
                    fire.push(j);
                }
                else if(mat[i][j]=='J')
                {
                    joy.push(i);
                    joy.push(j);
                }
            }
        }
        int cou =0;
        cross = true;
        broke = true;
        while(true)
        {
            cou++;
            bfsf();
            bfsj();
            if(broke == false|| cross== false)
            {
                break;
            }
        }
        if(broke == false)
        {
            printf("IMPOSSIBLE\n");
        }
        else if(cross == false)
        {
            printf("%d\n",cou);
        }
    }
}