Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2012-02-08SRM530 Div1(Practice)

SRM530 Div1 250 GogoXCake

| 02:26 | SRM530 Div1 250 GogoXCake - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM530 Div1 250 GogoXCake - SRM diary(Sigmar) SRM530 Div1 250 GogoXCake - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

一番上の列の一番左のマスは、カッターの一番上の一番左に当てはめないとダメに決まっているので左上からGreedyにカッターに当てはめていくだけ


ソースコード

class GogoXCake {
public:
	void examine(vector <string> &cake, vector <string> &cutter, int r, int c) {
		int ch=cutter.size(), cw=cutter[0].size();
		bool ok=true;
		for(int i=0; i<ch; i++) {
			for(int j=0; j<cw; j++) {
				if(!(cutter[i][j]=='X' || cake[r+i][c+j]=='.')) ok=false;
			}
		}
		if(!ok) return;
		for(int i=0; i<ch; i++) {
			for(int j=0; j<cw; j++) {
				if(cutter[i][j]=='.') cake[r+i][c+j]='X';
			}
		}
	}

	string solve(vector <string> cake, vector <string> cutter) {
		int h=cake.size(), w=cake[0].size();
		int ch=cutter.size(), cw=cutter[0].size();
		
		for(int i=0; i+ch<=h; i++) {
			for(int j=0; j+cw<=w; j++) {
				examine(cake, cutter, i, j);
			}
		}
		for(int i=0; i<h; i++) {
			for(int j=0; j<w; j++) {
				if(cake[i][j]=='.') return "NO";
			}
		}
		return "YES";
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120208