#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> #include<string> #include<vector> #include<queue> using namespace std; typedef long long LL; struct node{ int c; int tn; int tm; int num; node(int a,int b,int dd,int d) { c = a; tn = b; tm = dd; num = d; } node() { } }; struct node2{ int tn; int tm; int c; node2(int a,int b,int d) { tn = a; tm = b; c = d; } node2() { } }; bool cmp(node a,node b) { if(a.num!=b.num) { return a.num>b.num; } else if(a.c!=b.c) { return a.c<b.c; } else if(a.tn!=b.tn) { return a.tn<b.tn; } else { return a.tm<b.tm; } } int t,n,m,dx[]={0,1,-1,0},dy[]={1,0,0,-1}; string s[100]; int main() { cin>>t; while(t--) { cin>>n>>m; for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) s[i][j]='#'; for(int i=0;i<n;i++) cin>>s[i]; while(1) { vector<node>arr; arr.clear(); int book[100][100] = {0}; for(int i=0;i<=50;i++) for(int j=0;j<=50;j++) book[i][j]=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { if(!book[i][j]&&s[i][j]!='#') { int tc = 1; char c = s[i][j]; book[i][j] = 1; queue<node2>q; q.push(node2(i,j,s[i][j])); while(!q.empty()) { int sz = q.size(); for(int i=1;i<=sz;i++) { node2 temp = q.front(); q.pop(); int x = temp.tn; int y = temp.tm; for(int k = 0;k<4;k++) { int tempx = x+dx[k]; int tempy = y+dy[k]; if(tempx>=0&&tempx<n&&tempy>=0&&tempy<m&&!book[tempx][tempy]&&s[tempx][tempy]==c) { book[tempx][tempy] = 1; tc++; q.push(node2(tempx,tempy,c)); } } } } if(tc>1) { arr.push_back(node(s[i][j],i,j,tc)); } } } if(arr.size()==0) break; else { int ss; sort(arr.begin(),arr.end(),cmp); int xx = arr[0].tn; int yy = arr[0].tm; int cc = arr[0].c; queue<node2>q; q.push(node2(xx,yy,cc)); while(!q.empty()) { int sz = q.size(); for(int i=1;i<=sz;i++) { node2 temp = q.front(); q.pop(); int x = temp.tn; int y = temp.tm; int c = temp.c; for(int k = 0;k<4;k++) { int tempx = x+dx[k]; int tempy = y+dy[k]; if(tempx>=0&&tempx<n&&tempy>=0&&tempy<m&&s[tempx][tempy]==cc) { s[tempx][tempy]='#'; q.push(node2(tempx,tempy,c)); } } } } for(int i=0;i<m;i++) { int k = 0; for(int j=n-1;j>=0;j--) { if(s[j][i]=='#') { k++; } else s[j+k][i]=s[j][i]; if(k!=0) s[j][i]='#'; } } for(int i=0;i<m;i++) { int k=0; for(int j=0;j<n;j++) if(s[j][i]=='#') k++; if(k==n) { for(int j=0;j<n;j++) s[j][i]=s[j][i+1],s[j][i+1]='#'; } } } } int shu = 0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { if(s[i][j]=='#') shu++; } cout<<n*m-shu<<endl; } return 0; } 第三题