SRM530 medium(500) - avrmicom @ ウィキ

2012/1/26
161.65 points
約128分 <- 添字のミスに気づかず・・・

問題概要

ケーキを与えられた型を使って目的の形に切り抜く問題。逆に考えればテトリスみたいなパズルゲー。
ケーキと言っても長方形。入力は目的の形と切り抜きに使う型の形。切り抜けるかどうかを答える。

例

{"X.X"
,"..."
,"..."
,"X.X"}

{".X"
,".."
,"X."}

Returns: "YES"

解法

ケーキの上を型がZ字を描くように捜査していき、切り抜けるか調べていく。
４重ループになってしまったので複雑だった。

解答

#include <iostream>
#include <vector>
using namespace std;

class GogoXCake{
public:
	string solve(vector <string> cake, vector <string> cutter){
		vector<string> cake2;
		cake2 = cake;
		cout<<"#cake" << endl;
		PrintVector(cake2);
		cout << "#cutter" << endl;
		PrintVector(cutter);
		
		for(int y=0; y <= cake.size()-cutter.size(); y++){
			for(int x=0; x <= cake[0].size()-cutter[0].size(); x++){
				bool flag=true;
				cake=cake2;
				for(int yy=0; yy<cutter.size(); yy++){
					for(int xx=0; xx<cutter[0].size(); xx++){
						if(cutter[yy][xx]=='.'&&cake[yy+y][xx+x]=='.'){
							cake[yy+y][xx+x]='X';
							cout << 'x' ;
						}else if(cutter[yy][xx]=='.'&&cake[yy+y][xx+x]=='X'){
							flag=false;
							cout << 'f';
						}else{
							//do nothing
							cout << 't';
						}
					}
				}
				cout << " in in loop" << endl;
				cout << y << " " << x << endl;
				if(true==flag){
					cake2=cake;
				}
				PrintVector(cake2);
			}
		}
		cout << "out loop" << endl;
		PrintVector(cake2);
		
		bool flag2=true;
		for(int i=0; i<cake2.size(); i++){
			for(int j=0; j<cake2[0].size(); j++){
				if('X'!=cake2[i][j]){
					flag2=false;
				}
			}
		}
		
		if(flag2){
			return "YES";
		}else{
			return "NO";
		}
	}
	void PrintVector(vector <string> vec){
		for(int i=0; i<vec.size(); i++){
			cout<<vec[i]<<endl;
		}
		cout<<endl;
	}
};