kmjp's blog

競技プログラミング参加記です

Bayan 2015 Contest Warmup : C. Kamal-ol-molk's Painting

Bayan Warmupに参加。
ABCDを割とサクサク解けたと思ったら、Dで配列サイズを間違えるというしょうもないミス。
http://codeforces.com/contest/475/problem/C

問題

N*Mのグリッド上で筆を使って絵を描く。

筆の形状は長方形を成している。
ある位置に筆をおき、筆を右または下方向に1マスずつ移動して通過したマスを黒く塗っていき、ある時点で筆を上げる。
筆の移動中、筆はグリッドをはみ出てはならない。

最終的に得られた絵柄が与えられる。
この絵柄を生成できる最大面積の筆を答えよ。

解法

筆の幅・高さを総当たりする。

筆の開始位置は、筆の左上隅のセルが、グリッド上で最も上かつ左の黒マスに重なるようにしなければならない。
幅をW、高さをHとすると、筆は右と下のどちらかにしか動かせないので、筆の左上隅からH下かW右のいずれか片方のセルが黒いなら、そちらの方向に筆を動かす。
両方白または両方黒なら、そのサイズの筆で求める絵を描画できない。

上記手順を繰り返して全黒マスを通過できればOK。

一見計算量はO(H*W*(H+W))だが、大半は最初の1手目の移動ができないのでO((H+W)^2)程度で落ち着く。

int H,W;
string S[2001];
int sx,sy;

int SS[2002][2002];

int okok(int sy,int sx,int h,int w) {
	int a=SS[sy+h][sx+w]-SS[sy+h][sx]-SS[sy][sx+w]+SS[sy][sx];
	return a==w*h;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	sx=sy=-1;
	FOR(y,H) FOR(x,W) if(sy==-1 && S[y][x]=='X') sy=y,sx=x;
	FOR(y,H) FOR(x,W) if(S[y][x]=='X' && (y<sy || x<sx)) return _P("-1\n");
	FOR(y,H) {
		FOR(x,W) SS[y+1][x+1]=SS[y+1][x]+(S[y][x]=='X');
		FOR(x,W) SS[y+1][x+1]+=SS[y][x+1];
	}
	int mi=1<<30;
	int w,h;
	for(h=1;h<=H;h++) for(w=1;w<=W;w++) if(okok(sy,sx,h,w) && h*w<mi) {
		int ng=0;
		int tp=w*h;
		x=sx,y=sy;
		while(1) {
			int mr=0,md=0;
			if(x+w<W && S[y][x+w]=='X') mr=1;
			if(y+h<H && S[y+h][x]=='X') md=1;
			if(mr==md) break;
			if(mr) {
				tp+=h;
				x++;
			}
			else {
				tp+=w;
				y++;
			}
		}
		
		if(tp==SS[H][W]) mi=h*w;
	}
	
	
	if(mi==1<<30) _P("-1\n");
	else _P("%d\n",mi);
}

まとめ

問題設定が面白くてよかった。