ZJ-d365

#include <bits/stdc++.h>
#ifdef TEST
    #define debug(...) printf(__VA_ARGS__)
#else
    #define debug(...) (void)0
#endif
#define EB emplace_back
#define MP make_pair
#define ST first
#define ND second
using namespace std;
using ll = long long;
using llu = long long unsigned;
using pii = pair<int,int>;
/************************/
#define MAX 1000
int dx[4]={0,0,1,-1}, dy[4]={1,-1,0,0};
char mp[MAX+5][MAX+5];
bool vis[MAX+5][MAX+5];
int h,w;
inline bool check(int x, int y){
    return (x>=0) && (y >= 0) && (x < w) && (y < h);
}
int bfs(pii start){
    queue<pii> q;
    char targ = mp[start.ND][start.ST];
    int size = 0;
    if(!vis[start.ND][start.ST]){
        q.emplace(start);
        vis[start.ND][start.ST] = true;
    }
    while(!q.empty()){
        pii now = q.front(); q.pop();
        size++;
        for(int i=0;i<4;i++){
            pii fut = MP(now.ST+dx[i], now.ND+dy[i]);
            if(check(fut.ST, fut.ND) && !vis[fut.ND][fut.ST] && mp[fut.ND][fut.ST] == targ){
                vis[fut.ND][fut.ST] = true;
                q.emplace(fut);
            }
        }
    }
    return size;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int e=1;e<=n;e++){
        pii stat[26];
        for(int i=0;i<26;i++){
            stat[i].ND = i;
        }
        memset(mp,0x00,sizeof(mp));
        memset(vis,0x00,sizeof(vis));
        scanf("%d%d", &h, &w);
        for(int i=0;i<h;i++){
            scanf("%s",mp[i]);
        }
        for(int i=0;i<w;i++){
            for(int j=0;j<h;j++){
                debug("%c", mp[j][i]);
                stat[ mp[j][i]-'a' ].ST += (bfs(MP(i,j)) > 0);
            }
            debug("\n");
        }
        debug("DEBUG\n");
        for(int i=0;i<26;i++){
            debug("%c : %d\n", 'a'+i, stat[i].ST);
        }
        debug("=====SEPERATE=====\n");
        printf("World #%d\n", e);
        sort(stat,stat+26,[](const pii &a, const pii &b){
            return (a.ST == b.ST)? a.ND < b.ND : a.ST > b.ST;
        });
        for(int i=0;i<26;i++){
            if(stat[i].ST > 0)
                printf("%c: %d\n", 'a'+stat[i].ND, stat[i].ST);
        }
    }
    return 0;
}