657 - The die is cast(****)
2225 ワード
/*
,****
: ,* X , X ,
X 。 X
: arr , account X
: visit1 visit2, dfs1,dfs2
。
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int nMax=55;
int w,h;
char G[nMax][nMax];
bool visit[nMax][nMax];
int account[nMax];
struct Node
{
int x,y;
Node(){}
Node(int x,int y):x(x),y(y){}
};
struct Array
{
Node data[nMax*nMax];
int top;
Array(){top=0;}
}arr[nMax*nMax];
int u;
int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
bool check(int x,int y)
{
if(x>=0 && x<h && y>=0 && y<w)
return true;
return false;
}
void Init(int x,int y,int n)
{
visit[x][y]=1;
arr[n].data[arr[n].top++]=Node(x,y);
for(int i=0;i<4;i++)
{
int xx,yy;
xx=x+dir[i][0];
yy=y+dir[i][1];
if(check(xx,yy) && G[xx][yy]!='.' && !visit[xx][yy])
Init(xx,yy,n);
}
}
void dfs(int x,int y,int n)
{
visit[x][y]=1;
for(int i=0;i<4;i++)
{
int xx,yy;
xx=x+dir[i][0];
yy=y+dir[i][1];
if(check(xx,yy) && G[xx][yy]=='X' && !visit[xx][yy])
dfs(xx,yy,n);
}
}
int main()
{
//freopen("data.in","r",stdin);
int cas=1;
while(scanf("%d %d",&w,&h)==2)
{
if(w==0 && h==0)
break;
memset(G,0,sizeof(G));
memset(visit,0,sizeof(visit));
memset(account,0,sizeof(account));
memset(arr,0,sizeof(arr));//WA ,
printf("Throw %d
",cas++);
int n=0;
u=0;
for(int i=0;i<h;i++)
scanf("%s",G[i]);
for(int i=0;i<h;i++)
{
for(int j=0;j<w;j++)
{
if(!visit[i][j] && G[i][j]!='.')
Init(i,j,u++);
}
}
memset(visit,0,sizeof(visit));
for(int i=0;i<u;i++)
{
for(int j=0;j<arr[i].top;j++)
{
int xx,yy;
xx=arr[i].data[j].x;
yy=arr[i].data[j].y;
if(G[xx][yy]=='X' && !visit[xx][yy])
{
account[i]++;
dfs(xx,yy,i);
}
}
}
sort(account,account+u);
for(int i=0;i<u;i++)
{
if(i)
printf(" ");
printf("%d",account[i]);
}
printf("
");
}
return 0;
}