UVA 10034 Freckles

#include<bits/stdc++.h>
using namespace std;
long i;
double ans=0.0;
struct st
{
    long a,b;
    double wt;
    bool operator < ( const st&ck) const
    {
        return wt<ck.wt;
    }
};
vector<st>vec;
long ar[100007];
long  find(long r)
{
   return (ar[r]==r) ? r:  find(ar[r]);
}
long mst(long n1)
{
    sort(vec.begin(),vec.end());
    for(i=1;i<=n1;i++)
    ar[i]=i;
    long  count=0;
    ans=0;
    for(i=0;i<(long)vec.size();i++)
    {
        long a=find(vec[i].a);
        long b=find(vec[i].b);
        if(a!=b)
        {
            ar[a]=b;
            count++;
            ans+=vec[i].wt;
            if(count==n1-1)
            break;
        }
    }
}
main()
{
    long ts,cs=0;
    cin>>ts;
    while(ts--)
    {
        long node,j;
        cin>>node;
        double x[100003],y[100009];
        double rs;
        if(cs>0)
            cout<<endl;
        cs++;
        for(i=0;i<node;i++)
        {
            cin>>x[i]>>y[i];
        }
        for(i=0;i<node;i++)
        {
            for(j=i+1;j<node;j++)
            {
                rs=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                st edge;
                edge.a=i+1;
                edge.b=j+1;
                edge.wt=rs;
                vec.push_back(edge);
            }
        }
        mst(node);
        printf("%.2lf\n",ans);
        vec.clear();
    }
}

UVA 821 - Page Hopping

#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
long mp[110][110],i,k,j;
long floyd()
{
    for(k=0; k<101; k++)
    {
        for(i=0; i<101; i++)
        {
            for(j=0; j<101; j++)
            {
                mp[i][j]=min(mp[i][j],(mp[i][k]+mp[k][j]));
            }
        }
    }
}
using namespace std;
int main()
{
    long long a,b,cs=1;
    while(cin>>a>>b)
    {
        set<long>st;
        for(i=0; i<101; i++)
        {
            for(j=0; j<101; j++)
            {
                if(i!=j)
                {
                    mp[i][j]=1000000;
                }
                else
                    mp[i][j]=0;
            }
        }
        if(a==0&&b==0)
            break;
        st.insert(a);
        st.insert(b);
        mp[a][b]=1;
        long long a1,b1,sum=0;
        while(cin>>a1>>b1)
        {
            if(a1==0&&b1==0)
                break;
            st.insert(a1);
            st.insert(b1);
            mp[a1][b1]=1;
        }
        floyd();
        for(i=0; i<101; i++)
        {
            for(j=0; j<101; j++)
            {
                if(i!=j&&mp[i][j]!=1000000)
                {
                    sum=sum+mp[i][j];
                }
            }
        }
        long len=st.size();
        len=len*(len-1);
        double ans=(double)sum/len;
        printf("Case %ld: average length between pages = ",cs++);
        printf("%.3lf clicks\n",ans);
    }
}

UVA 10048 - Audiophobia

#include<bits/stdc++.h>
using namespace std;
#define mx 1000000
long mp[200][200],node;
long i,j,k;
long floyd()
{
    for(k=1;k<=node;k++)
    {
        for(i=1;i<=node;i++)
        {
            for(j=1;j<=node;j++)
            {
                mp[i][j]=min(mp[i][j],max(mp[i][k],mp[k][j]));
            }
        }
    }
}
main()
{
    long long edge,query,cs=0,ts=1;
    while(cin>>node>>edge>>query)
    {
        if(node==0&&edge==0&&query==0)
            break;
        if(cs>0)
            cout<<endl;
        cs++;
        for(i=1;i<=100;i++)
        {
            for(j=1;j<=100;j++)
            {
                if(i==j)
                    mp[i][j]==0;
                else
                    mp[i][j]=mx;
            }
        }
        long a,b,wt,sour,desti;
        for(i=1;i<=edge;i++)
        {
            cin>>a>>b>>wt;
            mp[a][b]=wt;
            mp[b][a]=wt;
        }
        floyd();
        printf("Case #%ld\n",ts++);
        for(i=1;i<=query;i++)
        {
            cin>>sour>>desti;
            if(mp[sour][desti]==mx||mp[sour][desti]==0)
            {
                printf("no path\n");
            }
            else
            {
                printf("%ld\n",mp[sour][desti]);
            }
        }
    }
}

UVA 11015 - 05-2 Rendezvous

#include<bits/stdc++.h>
using namespace std;
main()
{
    long n,m,cs=1;
    while(cin>>n>>m)
    {
        long i,j,k,a,b,wt,mp[100][100];
        string name[110];
        memset(mp,50, sizeof(mp));
        if(n==0&&m==0)
        {
            break;
        }
        for(i=1;i<=n;i++)
        {
            cin>>name[i];
        }
        for(i=1;i<=m;i++)
        {
            cin>>a>>b>>wt;
            mp[a][b]=min(mp[a][b],wt);
            mp[b][a]=min(mp[b][a],wt);
        }
        for(k=1;k<=n;k++)
        {
           for(i=1;i<=n;i++)
           {
               for(j=1;j<=n;j++)
               {
                   mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
               }
           }
        }
        long sum=0,mn=1000000000,indx=0;
        for(i=1;i<=n;i++)
        {
            sum=0;
            for(j=1;j<=n;j++)
            {
                if(i!=j)
                {
                    sum+=mp[i][j];
                }
            }
            if(sum<mn)
            {
                mn=sum;
                indx=i;
            }
        }
        printf("Case #%ld : ",cs++);
        cout<<name[indx]<<endl;
    }
}

All Shortest Path / Floyd Warshall algorithom

#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, t = 0;
    while(scanf("%d %d", &n, &m) == 2)
    {
        if(n == 0 && m == 0)
            break;
        char name[30][30];
        int map[30][30], x, y, v;
        int i, j, k;
        memset(map, 63, sizeof(map));
        for(i = 0; i < n; i++)
            scanf("%s", name[i]);
        while(m--)
        {
            scanf("%d %d %d", &x, &y, &v);
            x--, y--;
            map[x][y] = min(v, map[x][y]);
            map[y][x] = min(v, map[y][x]);
        }
        for(k = 0; k < n; k++)
            for(i = 0; i < n; i++)
                for(j = 0; j < n; j++)
                    map[i][j] = min(map[i][j], map[i][k]+map[k][j]);
        int ans = 0xfffffff, idx = 0, tmp;
        for(i = 0; i < n; i++)
        {
            tmp = 0;
            for(j = 0; j < n; j++)
                if(i != j)
                    tmp += map[i][j];
                    cout<<tmp<<endl;
            if(tmp < ans)
                ans =  tmp, idx = i;
        }
        printf("Case #%d : %s\n", ++t, name[idx]);
    }
    return 0;
}

Sort by using structure

#include<bits/stdc++.h>
using namespace std;
struct check
{
    string a,b;
    long w;
}data [2010];
///check data [2000];
///vector<check> e;

bool cmp(check f,check s)
{
    if(f.w==s.w)
        return f.a<s.a;

    else
        return f.w<s.w;
}

main()
{
    long ts,i,n,m;
    cin>>ts;
    while(ts--)
    {
        cin>>n>>m;
        string s,s1;
        long wt;
        for(i=0;i<m;i++)
        {
            cin>>s>>s1>>wt;
            data[i].a=s;
            data[i].b=s1;
            data[i].w=wt;
        }
        sort(data,data+n,cmp);
        for(i=0;i<m;i++)
        {
            cout<<data[i].a<<" "<<data[i].b<<" "<<data[i].w<<endl;

        }

    }
}

Sort by using pair by ordering any column(3 columns)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long n,w;
    string s,ss;
    cin>>n;
    vector<pair <int ,pair <string ,string> > > pr;
    for(int i=0;i<n;i++){
            cin>>s>>ss>>w;
        pr.push_back(make_pair(w,make_pair(s,ss)));
    }
    sort(pr.begin(),pr.end());

    for(int i=0;i<pr.size();i++){
        cout<<pr[i].first<<" "<<pr[i].second.first<<" "<<pr[i].second.second<<endl;
    }
}

UVA 544 - Heavy Cargo

problem hints:
Solution way:
             Create an arraylist for mapping, so that as you're taking the adjacencies in, you can just use                  arraylist.indexOf(x) to get the appropriate index you'll use for the adjacency matrix. In this                  process, if the arraylist does not contain the city already, just add it. The result is, you can just              do:

            int input = scan.nextInt();
            dist[arraylist.indexOf(a)][arraylist.indexOf(b)] = input;
            dist[arraylist.indexOf(b)][arraylist.indexOf(a)] = input;

            Then, run floyd warshall on the adjacency matrix with one modification - instead of taking the             min(dist[i][j], dist[i][k]+dist[k][j]), you have to take max(min(dist[i][k], dist[j][k]), dist[i][j])
Problem code:
#include<bits/stdc++.h>
using namespace std;
long i,j,k;
long vec[500][500];
long check(long n1)
{
    for(k=0;k<=n1;k++)
    {
        for(i=0;i<=n1;i++)
        {
            for(j=0;j<=n1;j++)
            {
                vec[i][j]=max(min(vec[i][k],vec[k][j]),vec[i][j]);
            }
        }
    }
}
main()
{
    long long n,m,cs=1;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=n;j++)
            {
                if(i==j)
                    vec[i][j]==0;
                else
                    vec[i][j]=-1;
            }
        }
        string s,s1;
        long wt,cnt=1;
        map<string,int>mp;
        for(i=1;i<=m;i++)
        {
            cin>>s>>s1>>wt;
            if(mp[s]==0)
            {
                mp[s]=cnt++;
            }
            if(mp[s1]==0)
            {
                mp[s1]=cnt++;
            }
            vec[mp[s]][mp[s1]]=wt;
            vec[mp[s1]][mp[s]]=wt;
        }
        check(n);
        cin>>s>>s1;
        long ans=vec[mp[s]][mp[s1]];
        printf("Scenario #%ld\n",cs++);
        cout<<ans<<" tons"<<endl<<endl;
    }
}

UVA 439 - Knight Moves

#include<bits/stdc++.h>
using namespace std;
int dr[]={-2,-2,+2,+2,+1,-1,+1,-1};
int dc[]={+1,-1,+1,-1,-2,-2,+2,+2};
queue<int>q;
int dist[100][100];
int sr,sc,er,ec;
int vis[100][100];
void bfs(int r,int c)
{
    vis[r][c]=1;
    dist[r][c]=0;
    q.push(r);
    q.push(c);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        int v=q.front();
        q.pop();
        for(int i=0;i<8;i++)
        {
            int row=dr[i]+u;
            int col=dc[i]+v;
            if(((row>=0&&row<8)&&(col>=0&&col<8))&&vis[row][col]==0)
            {
                vis[row][col]=1;
                dist[row][col]=dist[u][v]+1;
                q.push(row);
                q.push(col);
            }
        }
    }

}
main()
{
    string s,s1;
    while(cin>>s>>s1)
    {

        sr=int(s[0]-96);
        sc=s[1]-'0';
        er=int(s1[0]-96);
        ec=s1[1]-'0';
        memset(dist,0,sizeof(dist));
        memset(vis,0,sizeof(vis));
        bfs(sr-1,sc-1);
        cout<<"To get from "<<s<<" to "<<s1<<" takes "<<dist[er-1][ec-1]<<" knight moves."<<endl;
    }
}

Structure

স্ট্রাকচার (Structure)
Standard

স্ট্রাকচার হল কতগুলো স্ট্যান্ডার্ড ডাটা টাইপের সমষ্টিতে প্রোগ্রামারের নিজের সৃষ্টি করা ডাটা টাইপ। অন্যান্য ডাটা টাইপগুলো যেমন একটি নির্দিষ্ট ধরনের ডাটা রাখতে পারে, সেখানে স্ট্রাকচার একাধিক ধরনের একাধিক ডাটা রাখতে পারে। এই ডাটা টাইপটি প্রোগ্রামার নিজে তার প্রয়োজনমত তৈরি করে। এই ডাটা টাইপ অন্যান্য স্ট্যান্ডার্ড ডাটা টাইপের সমন্বয়ে তৈরি করা হয় বলে একে বলে Derived Data Type।

অনেক সময় কোন প্রবলেম সলভ করতে গেলে দেখা যায় যে কোন বিশেষ ধরনের বস্তুর জন্য কতগুলো করে তথ্য ভেরিয়েবলে রাখতে হয় যেগুলো দিয়ে পরবর্তিতে বিভিন্ন হিসাব করা হয়। সেই সব ক্ষেত্রে স্ট্রাকচার ব্যবহার করলে সবকিছু অনেক গোছানো থাকে। যেমন ধরা যাক একটি ক্লাসের 100 জন ছাত্রের নাম, রোল, বয়স এই তিনটা তথ্য ইনপুট নিয়ে রাখতে হবে। তাহলে তাহলে প্রতিটা ছাত্রের নামের জন্য একটা char অ্যারে, রোল এবং বয়সের জন্য দুটি int ভেরিয়েবল ডিক্লেয়ার করতে হবে। তাহলে 100 জন ছাত্রের জন্য এগুলোর প্রতিটার 100 এলিমেন্টের অ্যারে ডিক্লেয়ার করতে হবে।
1
2
 
char name[100][30];
int roll[100], age[100];

কিন্তু এইভাবে কাজ করা অনেক ঝামেলা। একদিকে দেখতেই কেমন যেন লাগে, তার উপর জিনিসটা গোছানো না। এছাড়া যদি এরকম অনেক ধরনের জিনিস থাকে যাদের সম্পর্কে তথ্য রাখতে হবে, অনেক হিসাব থাকে, তখন একেবারে হিজিবিজি অবস্থা হয়ে যাবে! এই ব্যাপারটাকেই অনেকখানি সুবিন্যস্ত এবং সুন্দর করে লেখা যায় স্ট্রাকচার ব্যবহার করলে। যেমন উপরের সমস্যাটার জন্যই একটা স্ট্রাকচার ডিক্লেয়ার করলে তা নিম্নরূপ হবেঃ
1
2
3
4
5
 
struct student {
    char name[30];
    int roll;
    int age;
};

এখন সিন্ট্যাক্স দেখা যাক। প্রথমে struct দিয়ে বলা হচ্ছে যে আমরা একটা স্ট্রাকচার ডিফাইন করতে যাচ্ছি। অর্থাৎ আমাদের এই নতুন ডাটা টাইপটা কিরকম হবে। যেহেতু এটা কোন স্ট্যান্ডার্ড ডাটা টাইপ না, এটায় বিভিন্ন টাইপের ডাটা থাকতে পারে, সেহেতু কি কি ডাটা থাকবে তা বলে দিতে হবে। এরপর যে student লেখা, এটা হল আমাদের নতুন ডাটা টাইপের নাম। আমরা যখন কোন ভেরিয়েবল ডিক্লেয়ার করি তখন ভেরিয়েবলের আগে ডাটা টাইপের নাম লেখা হয়। যেমন, int i; char c; এখানে int বা char হল ডাটা টাইপের নাম। সেরকম আমাদের নতুন এই ডাটা টাইপের নাম হল student।

এরপর { } এর মধ্যে আমরা কি কি ডাটা রাখব এই নতুন টাইপের অধীনে সেটা লিখে দিলাম। আমাদের student ডাটা টাইপের মধ্যে তিনটা তথ্য রাখতে হবে, নাম, রোল এবং বয়স। তাই নতুন এই ডাটা টাইপের মধ্যে কি কি ভেরিয়েবল থাকবে, সেটি কিরকম হবে তা আমরা এখানে বলে দিলাম। এরপর একটা সেমিকোলন দিয়ে শেষ করে দিলাম।

লক্ষ্যনীয়, এখানে যা যা করা হল এতক্ষণ, সবকিছু কেবল একটা ডাটা টাইপ ডিফাইন করল যার নাম student। এখনও কোন ভেরিয়েবল তৈরি করা হয়নি, অতএব কোন মেমরি বরাদ্দ করা হয়নি, এবং তাই এখনও এটি নিয়ে কোন কাজ করা যাবে না। এখন আমাদেরকে এরকম 100 জন ছাত্রের তথ্য রাখতে হবে। তাই আমরা এই student টাইপের 100 এলিমেন্ট বিশিষ্ট একটা অ্যারে ডিক্লেয়ার করব।
1
 
struct student stdnt[100];

এখানে আমরা একটা অ্যারে ডিক্লেয়ার করলাম। এটা অন্যান্য যেকোন অ্যারে এর মতই। পার্থক্য হল এটা একটা স্ট্রাকচারের অ্যারে। আর তাই এখানে শুরুতে ডাটা টাইপ বলার সময় পুরো কথাটা লিখতে হয়, struct student । এই ভেরিয়েবল ডিক্লেয়ারের কাজটা আলাদা করে না করে স্ট্রাকচার ডিফাইন করার সাথে সাথেই করা যায়।
1
2
3
4
5
 
struct student {
    char name[30];
    int roll;
    int age;
} stdnt[100];

এই কোডটি উপরের দুইটা কোডের মতই কাজ করবে। এখানে স্ট্রাকচার ডিফাইন করার সাথে সাথেই ভেরিয়েবল ডিক্লেয়ার করা হয়ে গেল। একাধিক ভেরিয়েবল ডিক্লেয়ার করতে হলে কমা দিয়ে দিয়ে আলাদা করে দিলেই হবে।

এখন যেহেতু স্ট্রাকচারের ভেরিয়েবল ডিক্লেয়ার করা হয়ে গেল, তাই ভেরিয়েবলগুলো নিয়ে এখন কাজ করা যাবে। ভেরিয়েবলগুলোর প্রতিটির মধ্যে তিনটি করে মেম্বার আছে, name, roll এবং age । এই মেম্বারগুলো ব্যবহার করার জন্য, অর্থাৎ এতে ইনপুট নিতে বা এর থেকে আউটপুট পেতে বা এই মানগুলো ব্যবহার করার জন্য বিশেষ সিন্ট্যাক্স রয়েছে।

এখানে আমাদের একেকটি ভেরিয়েবল হল stdnt[0], stdnt[1], … , stdnt[99] এগুলো। স্ট্রাকচারের অন্তর্ভুক্ত কোন একটি মেম্বার এক্সেস করতে হলে . (ডট) ব্যবহার করতে হয়। যেমন,
1
 
stdnt[0].roll = 10;

অতএব 100 জন ছাত্রের নাম, রোল, বয়স ইনপুট নেওয়া যাবে এভাবে।
1
2
3
4
 
int i;
for( i = 0; i < 100; i++ ) {
  scanf( "%s %d %d", stdnt[i].name, &stdnt[i].roll, &stdnt[i].age );
}

এখান থেকে খুব সহজেই বোঝা যাচ্ছে যে স্ট্রাকচারের প্রতিটা মেম্বার একেকটা ভেরিয়েবল হিসেবে কাজ করে, এবং সেইজন্য কেবল স্ট্রাকচার ভেরিয়েবলটার নাম দিয়ে সাথে ডট দিয়ে মেম্বারটি লিখে দিলেই হয়ে যায়। এভাবে করে অন্য যেকোন ভেরিয়েবল নিয়ে যেভাবে কাজ করা যায় সেভাবেই কাজ করা যাবে।

আমরা চাইলে এই স্ট্রাকচারের একটি ভেরিয়েবল ডিক্লেয়ার করার সময় অন্যান্য ভেরিয়েবলের মত সেটিকে initialize করতে পারি। int i = 0; লিখলে i নামক int ডিক্লেয়ার হওয়ার সাথে সাথে এতে 0 এসাইন করা হয়ে যায়। একই কাজ স্ট্রাকচারে করা যায়। ধরা যাক একটি স্ট্রাকচার টাইপ ডিফাইন করব আমরা যেটি হবে একটি box এর স্ট্রাকচার। এতে তিনটা মেম্বার থাকবে যারা একটি box এর দৈর্ঘ্য, প্রস্থ এবং উচ্চতা হবে।
1
2
3
4
5
 
struct box {
    int length;
    int width;
    int height;
};

এখন এই box টাইপের একটি ভেরিয়েবল b ডিক্লেয়ার করব আমরা যেটির length, width এবং height তিনটি ভেরিয়েবলকেই আমরা 0 দিয়ে initialize করব।
1
 
struct box b = { 0, 0, 0 };

এভাবে যেকোন স্ট্রাকচার ভেরিয়েবলকে initialize করা যায়। সেজন্য যতগুলো মেম্বার আছে তার প্রতিটার মান ক্রমানুসারে { } এর মধ্যে কমা দিয়ে আলাদা করে লিখে দিলেই হয়ে যাচ্ছে।

স্ট্রাকচারের একটা বড় সুবিধা হচ্ছে একটা স্ট্রাকচারকে আরেকটা স্ট্রাকচারে এসাইন করা যায় যদি দুইটা একই টাইপের হয়। অর্থাৎ ধরা যাক আমাদের box টাইপের দুটি স্ট্রাকচার ভেরিয়েবল আছে, b1 এবং b2 । তাহলে আমরা b1 = b2 এভাবে করে b2 স্ট্রাকচারকে b1 এ এসাইন করতে পারি। এতে যা হবে তা হল, b2 এর সবগুলা মেম্বারে যা যা মান আছে সেগুলো b1 এর অনুরূপ মেম্বারগুলোতে এসাইন হয়ে যাবে।

আরেকটা ব্যাপার হল যেকোন ডাটা টাইপের যেমন পয়েন্টার ডিক্লেয়ার করা যায় তেমনি স্ট্রাকচারেরও পয়েন্টার ডিক্লেয়ার করা যায়। যেমন box টাইপের একটা পয়েন্টার ডিক্লেয়ার করা যায় এভাবে,
1
 
struct box *b;

এভাবে আমরা b নামক একটা পয়েন্টার ডিক্লেয়ার করলাম। কিন্তু যেহেতু মেমরি এলোকেট করা হয়নি তাই এটি নিয়ে এখনও কাজ করা যাবে না। এই ব্যাপারে বুঝতে হলে পয়েন্টার সম্পর্কে ভালো ধারণা থাকা প্রয়োজন। এই লেখাটি পড়লে আশা করি অনেকখানি পরিষ্কার হয়ে যাবে। এখন আমরা মেমরি এলোকেট করে নিব, তারপর কাজ করব।
1
 
b = ( struct box * ) malloc( sizeof( struct box ) );

এই b যেহেতু ভেরিয়েবল না, পয়েন্টার, তাই এর মাধ্যমে মেম্বার এক্সেস করতে হলে . (ডট) এর পরিবর্তে -> (তীর চিহ্ন) ব্যবহার করতে হয়। যেমন,

1
2
3
 
b->length = 10;
scanf( "%d", &b->width );
printf( "%d", b->height );

মূলত এগুলোই হল স্ট্রাকচারের বেসিক। বিভিন্ন ডাটা স্ট্রাকচারে এই স্ট্রাকচার ব্যবহার করা হয়। যেমন স্ট্যাক, কিউ, ট্রি এইসব ডাটা স্ট্রাকচারের মূল ভিত্তি হল স্ট্রাকচার। তাই স্ট্রাকচার কিভাবে ব্যবহার করতে হয়, এবং কিভাবে এটি কাজ করে তা জানা থাকা গুরুত্বপূর্ণ।

UVA 11900 - Boiled Eggs

#include <stdio.h>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
        {
            long n,p,q,i,ar[100]={0};
            cin>>n>>p>>q;
            for(i=1;i<=n;i++)
            {
                cin>>ar[i];
            }
            long sum=0,cnt=0;
            for(i=1;i<=n;i++)
            {
                sum+=ar[i];
                if(sum>q||cnt>=p)
                {
                    break;
                }
                cnt++;
            }
            printf("Case %ld: %ld\n",cs++,cnt);
        }
 }

UVA 10336 - Rank the Languages

#include<bits/stdc++.h>
#define MAX 1111
using namespace std;
map<pair<int,int>,int>vis;
map<char,int>mp;
char s[1010][1010];
int dx[]={-1,0,0,1};
int dy[]={0,-1,1,0};
int n,m;
long dfs(long x,long y,long ch1)
{
    int i1;
    vis[make_pair(x,y)]=1;
    for(i1=0;i1<4;i1++)
    {
        int x1=x+dx[i1];
        int y1=y+dy[i1];
        if((vis[make_pair(x1,y1)]==0)&&(s[x1][y1]==ch1)&&(x1>=1&&x1<=n)&&(y1>=1&&y1<=m))
        {
            vis[make_pair(x1,y1)]==1;
            dfs(x1,y1,ch1);
        }
    }
}
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        cin>>n>>m;
        int i,j,mx=0;
        char ch;
        vis.clear();
        mp.clear();
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                cin>>s[i][j];
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(vis[make_pair(i,j)]==0)
                {
                    ch=s[i][j];
                    mp[ch]++;
                    dfs(i,j,ch);
                    if(mp[ch]>mx)
                    {
                        mx=mp[ch];
                    }
                }
            }
        }
        cout<<"World #"<<cs++<<endl;
        for(i=mx;i>0;i--)
            for(j=97;j<=122;j++)
                {
                    ch=j;
                    if(mp[ch]==i)
                    cout<<ch<<": "<<i<<endl;
                }
    }
}

UVA 11244 - Counting Stars

#include<bits/stdc++.h>
#define MAX 1111
using namespace std;
int cnt=0,vis[101][101],r,i,c,j;
char s[101][101];
int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,-1,0,1};
int dfs(int x,int y)
{
    int i1;
    cnt++;
    vis[x][y]=1;
    for(i1=0;i1<8;i1++)
    {
        int x1=x+dx[i1];
        int y1=y+dy[i1];
        if((x1>=0&&x1<r)&&(y1>=0&&y1<c)&&(vis[x1][y1]==0)&&(s[x1][y1]=='*'))
        {
            vis[x1][y1]=1;
            dfs(x1,y1);
        }
    }
    return cnt;
}
main()
{
    while(cin>>r>>c)
    {
        getchar();
        if(r==0&&c==0)
            break;
        for(i=0;i<r;i++)
        {
            for(j=0;j<c;j++)
            {
                cin>>s[i][j];
            }
        }
        int ans=0;
        for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    if((vis[i][j]==0)&&(s[i][j]=='*'))
                    {
                        vis[i][j]=1;
                        cnt=0;
                        cnt=dfs(i,j);
                        if(cnt==1)
                            ans++;
                    }
                }
            }
            cout<<ans<<endl;
            memset(vis,0,sizeof(vis));
            memset(s,'\0',sizeof(s));
    }
}

UVA 10684 - The jackpot

#include<bits/stdc++.h>
#define MAX 1111
using namespace std;
main()
{
    long n;
    while(cin>>n)
    {
        long long mx=-1,ar[100010]={0},i,sum=0;
        if(n==0)
            break;
        ar[n+10];
        for(i=0;i<n;i++)
        {
            cin>>ar[i];
        }
        for(i=0;i<n;i++)
        {
            sum+=ar[i];
            if(sum<0)
                sum=0;
            else if(sum>mx)
            {
                mx=sum;
            }
        }
        if(mx<=0)cout<<"Losing streak.\n";
        else cout<<"The maximum winning streak is "<<mx<<".\n";
    }
}

UVa : 469 (Wetlands of Florida)

#include<bits/stdc++.h>
#define MAX 1111
using namespace std;
int cnt=0,vis[101][101],n,i;
char s1[101][101],s[101];
int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,-1,0,1};
int dfs(int r,int c)
{
    cnt++;
    vis[r][c]=1;
    int x1,y1,i1;
    for(i1=0;i1<8;i1++)
    {
        x1=r+dx[i1];
        y1=c+dy[i1];
        if((x1>=0&&x1<i)&&(y1>=0&&y1<n)&&(vis[x1][y1]==0)&&(s1[x1][y1]=='W'))
        {
            vis[x1][y1]=1;
            dfs(x1,y1);
        }
    }
    return cnt;
}
main()
{
    int ts,cs=1;
    cin>>ts;
    getchar();
    getchar();
    while(ts--)
    {
        if(cs!=1)
            cout<<endl;
        cs++;
        i=0;
        n=0;
        while(gets(s)&&strlen(s)>0)
        {
            if(s[0]=='L'||s[0]=='W')
            {
                strcpy(s1[i],s);
                i++;
                n=strlen(s);
            }
            else
            {
                int row,col;
                sscanf(s, "%d %d", &row, &col);
                cnt=0;
                cnt=dfs(row-1,col-1);
                cout<<cnt<<endl;
                memset(vis,0,sizeof(vis));
            }
        }
    }
}

UVA 260 - Il Gioco dell'X

#include<bits/stdc++.h>
#define MAX 1111
using namespace std;
char s[MAX][MAX];
int vis[MAX][MAX],n;
int dx[6]={-1,-1,0,0,1,1};
int dy[6]={-1,0,-1,1,0,1};
int dfs(int x,int y)
{
    int x1,y1,x2,y2,i1;
    queue<int>q;
    q.push(x);
    q.push(y);
    vis[x][y]=1;
    while(!q.empty())
    {
        x2=q.front();
        q.pop();
        y2=q.front();
        q.pop();
        for(i1=0;i1<6;i1++)
        {
            x1=x2+dx[i1];
            y1=y2+dy[i1];
            if((x1>=1&&x1<=n)&&(y1>=1&&y1<=n)&&(vis[x1][y1]==0)&&(s[x1][y1]=='w'))
            {
                vis[x1][y1]=1;
                q.push(x1);
                q.push(y1);
            }
        }
    }
}
main()
{
    long cs=1;
    while(cin>>n)
    {
        if(n==0)
            break;
        int i,j;
        getchar();
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                cin>>s[i][j];
            }
        }
        for(i=1;i<=n;i++)
        {
            if(s[i][1]=='w'&&vis[i][1]==0)
            {
                dfs(i,1);
            }
        }
        int flag=0;
        for(i=1;i<=n;i++)
        {
            if(vis[i][n]==1)
            {
                flag=1;
                break;
            }
        }
        if(flag==1)
        {
            printf("%d W\n",cs++);
        }
        else
            printf("%d B\n",cs++);
        memset(vis,0,sizeof(vis));
        memset(s,'\0',sizeof(s));
    }
}

UVA 459 - Graph Connectivity

#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
vector<long>vec[100];
long vis[100]={0},i,j;
long bfs(long source)
{
    long u,v;
    queue<long>que;
    vis[source]=1;
    que.push(source);
    while(!que.empty())
    {
        long u=que.front();
        for(i=0;i<vec[u].size();i++)
        {
            v=vec[u][i];
            if(vis[v]==0)
            {
                que.push(v);
                vis[v]=1;
            }
        }
        que.pop();
    }
}
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        char ch;
        string s;
        long k,k1,k2,i,cnt=0,k3=0,ar[100]={0},vi[100]={0},i1,cnt1=0;
        memset(vis,0,sizeof(vis));
        cin>>ch;
        k=ch-64;
        if(cs!=1)
        {
            cout<<endl;
        }
        cs++;
        getchar();
        while(getline(cin,s))
        {
            if(s[0]=='\0')
                break;
            k1=s[0]-64;
            k2=s[1]-64;
            vec[k1].push_back(k2);
            vec[k2].push_back(k1);
            if(vi[k1]==0)
            {
                cnt1++;
                ar[k3++]=k1;
                vi[k1]=1;
            }
            if(vi[k2]==0)
            {
                ar[k3++]=k2;
                cnt1++;
                vi[k2]=1;
            }
        }
        sort(ar,ar+k3);
        for(i=0;i<k3;i++)
        {
            i1=ar[i];
            if(vis[i1]==0)
            {
                cnt++;
                vis[i1]=1;
                bfs(i1);
            }
        }
        cnt+=(k-cnt1);
        cout<<cnt<<endl;
        for(i=0;i<=30;i++)
        {
            vec[i].clear();
        }
    }
}

longest path in a grid by dfs

#include <stdio.h>

#include <string.h>

#include<bits/stdc++.h>

using namespace std;

long dx[]={-1,-1,-1,0,0,1,1,1};

long dy[]={-1,0,1,-1,1,-1,0,1};

char s[30][30];

long n,vis[100][100]={0},len,cnt=0,i,j;

long dfs(long x,long y)

{

    vis[x][y]=1;

    long i1;

    cnt++;

    for(i1=0;i1<8;i1++)

    {

        long x1=x+dx[i1];

        long y1=y+dy[i1];

        if((x1>=0&&x1<len)&&(y1>=0&&y1<len)&&(s[x1][y1]=='1')&&(vis[x1][y1]==0))

        {

            vis[x1][y1]=1;

            dfs(x1,y1);

        }

    }

    return cnt;

}

int main()

{

    long cs=1,ts,i2;

    cin>>ts;

    getchar();

    getchar();

    while(ts--)

    {

        i2=0;

        long mx;

        memset(s,'\0',sizeof(s));

        if(cs!=1)

            cout<<endl;

            cs++;

        memset(vis,0,sizeof(vis));

        while(gets(s[i2]))

        {

            if(s[i2][0]=='\0')

                break;

            i2++;

        }

        len=i2;

        mx=0;

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

        {

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

            {

                if(s[i][j]=='1')

                {

                    cnt=0;

                    dfs(i,j);

                    mx=max(mx,cnt);

                }

            }

        }

        cout<<mx<<endl;

    }

}

UVA 871 - Counting Cells in a Blob

#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
long dx[]={-1,-1,-1,0,0,1,1,1};
long dy[]={-1,0,1,-1,1,-1,0,1};
char s[30][30];
long n,vis[100][100]={0},len,cnt=0,i,j;
long dfs(long x,long y)
{
    vis[x][y]=1;
    long i1;
    cnt++;
    for(i1=0;i1<8;i1++)
    {
        long x1=x+dx[i1];
        long y1=y+dy[i1];
        if((x1>=0&&x1<len)&&(y1>=0&&y1<len)&&(s[x1][y1]=='1')&&(vis[x1][y1]==0))
        {
            vis[x1][y1]=1;
            dfs(x1,y1);
        }
    }
    return cnt;
}
int main()
{

    long cs=1,ts,i2;
    cin>>ts;
    getchar();
    getchar();
    while(ts--)
    {
        i2=0;
        long mx;
        memset(s,'\0',sizeof(s));
        if(cs!=1)
            cout<<endl;
            cs++;
        memset(vis,0,sizeof(vis));
        while(gets(s[i2]))
        {
            if(s[i2][0]=='\0')
                break;
            i2++;
        }
        len=i2;
        mx=0;
        for(i=0; i<len; i++)
        {
            for(j=0;j<len;j++)
            {
                if(s[i][j]=='1')
                {
                    cnt=0;
                    dfs(i,j);
                    mx=max(mx,cnt);
                }
            }
        }
        cout<<mx<<endl;
    }
}

UVA 572 - Oil Deposits

#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
long dx[]={-1,-1,-1,0,0,1,1,1};
long dy[]={-1,0,1,-1,1,-1,0,1};
char s[130][130];
long n,vis[500][500]={0},m;
void dfs(long x,long y)
{
    vis[x][y]=1;
    long i1;
    for(i1=0;i1<8;i1++)
    {

        long x1=x+dx[i1];
        long y1=y+dy[i1];
        if((x1>=0&&x1<n)&&(y1>=0&&y1<m)&&(s[x1][y1]=='@')&&(vis[x1][y1]==0))
        {
            vis[x1][y1]=1;
            dfs(x1,y1);
        }
    }
}
main()
{
    long cs=1;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        long cnt=0,i,j;
        getchar();
        memset(vis,0,sizeof(vis));
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                cin>>s[i][j];
            }
        }
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                if(s[i][j]=='@'&&vis[i][j]==0)
                {
                    vis[i][j]=1;
                    dfs(i,j);
                    cnt++;
                }
            }
        }
        cout<<cnt<<endl;
    }
}

UVA 352 - The Seasonal War

#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
long dx[]={-1,-1,-1,0,0,1,1,1};
long dy[]={-1,0,1,-1,1,-1,0,1};
char s[30][30];
long n,vis[500][500]={0};
void dfs(long x,long y)
{
    vis[x][y]=1;
    long i1;
    for(i1=0; i1<8; i1++)
    {
        long x1=x+dx[i1];
        long y1=y+dy[i1];
        if(((x1>=0&&x1<n)&&(y1>=0&&y1<n))&&vis[x1][y1]==0)
        {
            vis[x1][y1]=1;
            if(s[x1][y1]=='1')
                dfs(x1,y1);
        }
    }
}
main()
{
    long cs=1;
    while(cin>>n)
    {
        long cnt=0,i,j;
        getchar();
        memset(vis,0,sizeof(vis));
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
                cin>>s[i][j];
            }
        }
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
                if(vis[i][j]==0 && s[i][j]=='1')
                {
                    vis[i][j]=1;
                    dfs(i,j);
                    cnt++;
                }
            }

        }
        printf("Image number %ld contains %ld war eagles.\n",cs++,cnt);
    }
}

UVA 138 - Street Numbers

#include<bits/stdc++.h>
using namespace std;
main()
{
    long long n,x=8,cnt=0;
    double n2;
    while(1)
    {
        n2=sqrt((x*x+x)/2);
        n=n2;
        if(n==n2)
        {
            printf("%10lld%10lld\n",n,x);
            cnt++;
        }
        if(cnt==10)
        break;
        x++;
    }

}

UVA 11080 - Place the Guards

#include<bits/stdc++.h>
using namespace std;
long i,vis[100000]={0};
vector<long>vec[10000];
int bfs(int n)
{
    queue<int>q;
    q.empty();
    long tt[100003]={0},c1=0,c2=1;
    q.push(n);
    vis[n]=1;
    tt[n]=1;
    while(!q.empty())
    {
        int u=q.front();
          q.pop();
          vis[u]=1;
        for(int i=0;i<vec[u].size();i++)
        {
            int v=vec[u][i];
            if(vis[v]==0)
            {
              q.push(v);
              vis[v]=1;
              if(tt[u]==1)
              {
                 tt[v]=2;
                 c1++;
              }
              if(tt[u]==2)
              {
                  tt[v]=1;
                  c2++;
              }
            }
            else
            {
                  if(tt[u]==tt[v])
                    return -1;
            }
        }
    }
    c1=min(c1,c2);
    return c1;
}
main()
{
    long ts;
    cin>>ts;
    while(ts--)
    {
        long a,b,x,y,ans,rs=0;
        cin>>a>>b;
        for(i=0;i<a+5;i++)
        {
            vis[i]=0;
            vec[i].clear();
        }
        for(i=0;i<b;i++)
        {
            cin>>x>>y;
            vec[x].push_back(y);
            vec[y].push_back(x);
        }
        for(i=0;i<a;i++)
        {
            if(vis[i]==0)
            {
                if(vec[i].size()>0)
                {
                    ans=bfs(i);
                    if(ans==-1)
                        break;
                    rs=rs+ans;
                }
                else
                   rs+=1;
            }
            if(ans==-1)
                break;
        }
        if(ans==-1)
            cout<<-1<<endl;
        else
            cout<<rs<<endl;
    }
}