10336 - Rank the Languages.cpp

#include<bits/stdc++.h>
using namespace std;

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
char a[1000][1000];
bool visited[1000][1000];
int r,c;

struct gg{
    char a;
    int b;
}rr[30];


bool cmp(gg x,gg y){

    if(x.b==y.b) return x.a<y.a;
    return x.b>y.b;

}

map<char,int>m;

void dfs(int x,int y){

    visited[x][y]=true;

    for(int i=0;i<4;i++){
        int xx = x+dx[i];
        int yy = y+dy[i];

        if(visited[xx][yy]==false && a[xx][yy]==a[x][y] && xx>=0 && yy>=0 && xx<r && yy<c){
            dfs(xx,yy);
        }

    }

}

int main(){

    int t;

    cin>>t;

    for(int i=1;i<=t;i++){

        cin>>r>>c;
        getchar();

        memset(visited,false,sizeof(visited));

        for(int j=0;j<r;j++){
            cin>>a[j];
        }

        char ra[30];
        int q=0;
        for(int j=0;j<r;j++){
            for(int k=0;k<c;k++){
                if(visited[j][k]==false){
                    if(m.find(a[j][k])==m.end()){
                        m[a[j][k]]=1;
                        ra[q]=a[j][k];
                        q++;

                    }
                    else m[a[j][k]]++;

                    dfs(j,k);
                }
            }
        }

        printf("World #%d\n",i);

        for(int j=0;j<q;j++){
            //cout<<ra[j]<<": "<<m[ra[j]]<<"\n";
            rr[j].a=ra[j];
            rr[j].b=m[ra[j]];
        }

        sort(rr,rr+q,cmp);

        for(int j=0;j<q;j++){
            cout<<rr[j].a<<": "<<rr[j].b<<"\n";
        }

        m.clear();

    }

}