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; }