1028-Square Carpets

解法

左上を優先的に消していく、かなり怪しい貪欲法で解いた

実装(C++)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <valarray>
#include <cstring>
using namespace std;
struct Remove{
	int x,y,size;
};
struct Board{
	int W,H;
	int data[20];
	int clear_size[10][10];
	int count;
	Board(){
		memset(data,0,sizeof(data));
		count=0;
	}
	inline int get(int x,int y){
		return (data[x]>>y)&1;
	}
	inline int set(int x,int y,int val){
		if(val)
			data[x]|=(1<<y);
		else
			data[x]&=~(1<<y);
	}
	void show(){
		cout<<"---DELETE DATA---"<<endl;
		for(int y=0;y<H;y++){
			for(int x=0;x<W;x++){
				cout<<clear_size[x][y]<<" ";
			}
			cout<<endl;
		}
		cout<<"---DELETE DATA END---"<<endl;
	}
	void remove(int x,int y,int size){
		int clear=~(((1<<(y+size))-1)-((1<<y)-1));
		for(int xx=x;xx<x+size;xx++){
			data[xx]&=clear;
		}
	}
	bool check(int x,int y,int size){
		if(x+size>W||y+size>H)return false;

		int chkdata=(((1<<(y+size))-1)-((1<<y)-1));
		for(int xx=x;xx<x+size;xx++){
			if((data[xx]|chkdata)!=data[xx])return false;
		}
		return true;
	}
	bool cover(int x1,int y1,int x2,int y2){
		int d1[10],d2[10];
		memset(d1,0,sizeof(d1));
		memset(d2,0,sizeof(d2));
		if(x1==x2&&y1==y2)return false;
		int s1=clear_size[x1][y1],s2=clear_size[x2][y2];
		int c1=(((1<<(y1+s1))-1)-((1<<y1)-1)),c2=(((1<<(y2+s2))-1)-((1<<y2)-1));
		for(int x=x1;x<x1+s1;x++){
			d1[x]=data[x]&c1;
		}
		for(int x=x2;x<x2+s2;x++){
			d2[x]=data[x]&c2;
		}
		for(int x=0;x<W;x++){
			if((d1[x]|d2[x])!=d1[x])return false;
		}
		return true;
	}
	void pre_clear(){
		for(int x1=0;x1<W;x1++){
			for(int y1=0;y1<H;y1++){
				for(int x2=0;x2<W;x2++){
					for(int y2=0;y2<H;y2++){
						if(cover(x1,y1,x2,y2)){
							clear_size[x2][y2]=0;
							//cout<<x2<<","<<y2<<endl;

						}
					}
				}
			}
		}
	}
	void init(){
		for(int y=0;y<H;y++){
			for(int x=0;x<W;x++){
				for(int sze=0;;sze++){
					if(check(x,y,sze))clear_size[x][y]=sze;else break;
				}
			}
		}
		pre_clear();
	}
	void solve_one(){
		for(int y=0;y<H;y++){
			for(int x=0;x<W;x++){
				int cnt=0;
				if(get(x,y)==0)continue;
				for(int xx=0;xx<W;xx++){
					for(int yy=0;yy<H;yy++){
						if(xx<=x&&x<xx+clear_size[xx][yy]){
							if(yy<=y&&y<yy+clear_size[xx][yy]){
								cnt++;
							}
						}
					}
				}
				if(cnt==1){
					count++;
					for(int xx=0;xx<W;xx++){
						for(int yy=0;yy<H;yy++){
							if(xx<=x&&x<xx+clear_size[xx][yy]){
								if(yy<=y&&y<yy+clear_size[xx][yy]){
									remove(xx,yy,clear_size[xx][yy]);
								}
							}
						}
					}
				}
			}

		}
	}
	vector<Remove> get_remove(){
		vector<Remove> res;
		for(int x=0;x<W;x++){
			for(int y=0;y<H;y++){
				Remove t;
				t.x=x,t.y=y;
				if(clear_size[x][y]){
					t.size=clear_size[x][y];
					res.push_back(t);
				}
			}
		}
		return res;
	}
	bool empty(){
		for(int x=0;x<W;x++){
			if(data[x]!=0)return false;
		}
		return true;
	}
};

istream &operator>>(istream &is,Board &b){
	cin>>b.W>>b.H;
	for(int y=0;y<b.H;y++){
		for(int x=0;x<b.W;x++){
			int t;
			cin>>t;
			b.set(x,y,t);
		}
	}
	b.init();
	return is;
}

ostream &operator<<(ostream &os,Board &b){
	os<<"---MAP-DATA-BEGIN---"<<endl;

	for(int y=0;y<b.H;y++){
		for(int x=0;x<b.W;x++){
			os<<b.get(x,y)<<" ";
		}
		os<<endl;
	}
	os<<"---MAP-DATA-END---"<<endl;

	return os;
}


int main(){
	for(;;){
		Board data;
		cin>>data;
		if(data.W*data.H==0)break;
		while(data.empty()==false){
			int back=data.count;
			while(1){
				data.solve_one();
				data.pre_clear();
				if(back==data.count)break;
				back=data.count;
			}
			vector<Remove> r=data.get_remove();
			if(r.empty()==false){
				data.remove(r[0].x,r[0].y,r[0].size);
				data.pre_clear();
				data.count++;
			}
		}
		//data.show();
		//cout<<endl<<data.count<<endl;
		//cout<<data<<endl;
		cout<<data.count<<endl;
	}
}