PKU 3923 Ugly Windows

問題

nxmのグリッドで表されるウィンドウの図がある。
このうち最前面にあるウィンドウを全て答えよ。

制約条件

n,m≦100

方針

出現するアルファベットについてそれぞれ最も左右上下の座標を覚えておく。
その長方形の範囲が、

• 一辺の長さが3以上
• 周囲はそのアルファベット
• 内部は全て'.'

ならば、そのアルファベットのウィンドウは前面にある。

ソースコード

int h,w; char in[100][101];
int l[26],r[26],t[26],b[26];

bool ok(int c){
	if(l[c]==inf || l[c]+1>=r[c] || t[c]+1>=b[c])return 0;
	
	for(int y=t[c];y<=b[c];y++)
	for(int x=l[c];x<=r[c];x++)
	if(in[y][x]!= (y==t[c]||y==b[c]||x==l[c]||x==r[c]?'A'+c:'.'))return 0;
	
	return 1;
}

int main()
{
	while(scanf("%d%d",&h,&w),h){
		rep(i,26)l[i]=t[i]=inf, r[i]=b[i]=-1;
		
		rep(i,h){
			scanf("%s",in[i]);
			rep(j,w)if(in[i][j]!='.'){
				int c=in[i][j]-'A';
				l[c]=min(l[c],j); r[c]=max(r[c],j);
				t[c]=min(t[c],i); b[c]=max(b[c],i);
			}
		}
		
		rep(i,26)if(ok(i))printf("%c",'A'+i); puts("");
	}
	return 0;
}