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; } }