|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <iostream> #include <cstdio> #include <vector> #include <stack> #include <queue> #include <cmath> #include <cstring> #include <fstream> #include <string> #include <algorithm> #define INF 1000000000 #define ll long long using namespace std; int h,w; string arr[1010]; bool visit[1010][1010]; int stateCount[26]; struct stateInfo{ int count; int name; }; vector<stateInfo> vb; bool cmp(stateInfo a,stateInfo b) { if(a.count!=b.count) return a.count>b.count; else return a.name<b.name; } void findSet(int a,int b) { char c = arr[a][b]; int x,y; queue<int> cue; cue.push(a); cue.push(b); visit[a][b]=1; while(!cue.empty()) { x = cue.front();cue.pop(); y = cue.front();cue.pop(); if(x+1<h && arr[x+1][y]==c && visit[x+1][y]==0) { visit[x+1][y]=1; cue.push(x+1); cue.push(y); } if(x-1>=0 && arr[x-1][y]==c && visit[x-1][y]==0) { visit[x-1][y]=1; cue.push(x-1); cue.push(y); } if(y+1<w && arr[x][y+1]==c && visit[x][y+1]==0) { visit[x][y+1]=1; cue.push(x); cue.push(y+1); } if(y-1>=0 && arr[x][y-1]==c && visit[x][y-1]==0) { visit[x][y-1]=1; cue.push(x); cue.push(y-1); } } } int main() { int t,kase=1; scanf("%d",&t); stateInfo tmp; getchar(); while(t--) { cin>>h; getchar(); cin>>w; getchar(); vb.clear(); memset(visit,0,sizeof(visit)); memset(stateCount,0,sizeof(stateCount)); for(int i=0;i<h;i++) { getline(cin,arr[i]); } for(int i=0;i<h;i++) { for(int j=0;j<w;j++) { if(visit[i][j]==0) { findSet(i,j); stateCount[arr[i][j]-'a']+=1; } } } cout<<"World #"<<kase++<<"\n"; for(int i=0;i<26;i++) { if(stateCount[i]!=0) { //cout<<char('a'+i)<<": "<<stateCount[i]<<"\n"; tmp.name = i; tmp.count = stateCount[i]; vb.push_back(tmp); } } sort(vb.begin(),vb.end(),cmp); for(int i=0;i<vb.size();i++) { cout<<char(vb[i].name+'a')<<": "<<vb[i].count<<"\n"; } } return 0; } |