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;
}