Problem 1211 : Trapezoids

問題概要

テキストで*により台形がいくつか書かれている。
各辺の長さは3以上であり、二つの辺は水平である。
台形は辺同士が接触することはない。

このとき出現する台形を、面積ごとにその個数を出力せよ。

解法

入力を見ていき、'*'があったらそこから（時計回りに）伸びる台形を消す。
条件より最初の*は左上の頂点。
また、*が曲がるところが他の頂点なので、その点は記憶しておく。

ソースコード

int dx[]={-1,0,1,1,1,0,-1,-1},dy[]={-1,-1,-1,0,1,1,1,0};
int h;
char in[1000][82];
int Y[5],X[5],n;
map<int,int> M;

void dfs(int y,int x,int pd)
{
	in[y][x]=' ';
	int ny=y+dy[pd],nx=x+dx[pd];
	if(ny<0||nx<0||ny>=h||!in[ny][nx]||in[ny][nx]!='*')
	{
		Y[n]=y; X[n]=x; n++;
		rep(d,7)
		{
			pd=pd+1&7;
			ny=y+dy[pd],nx=x+dx[pd];
			if(ny<0||nx<0||ny>=h||!in[ny][nx])continue;
			if(in[ny][nx]=='*')goto FOUND;
		}
		return; FOUND:;
	}
	dfs(ny,nx,pd);
}
int main()
{
	bool f=1;
	while(scanf("%d",&h),h)
	{
		if(!f)puts("----------"); else f=0;
		
		M.clear(); getchar();
		rep(i,h)fgets(in[i],81,stdin),in[i][strlen(in[i])-1]=0;
		
		rep(i,h)for(int j=0;in[i][j];j++)if(in[i][j]=='*')
		{
			n=1; Y[0]=i; X[0]=j;
			dfs(i,j,3);
			M[(Y[3]-Y[0]+1)*(X[1]-X[0]+X[2]-X[3]+2)/2]++;
		}
		fr(i,M)printf("%d %d\n",i->first,i->second);
	}
	return 0;
}