UVA - 1602 Lattice Animals (暴力+同构判定)

题目链接

题意：求能放进w*h的网格中的不同的n连通块个数(通过平移/旋转/翻转后相同的算同一种)，1<=n<=10,1<=w,h<=n。

刘汝佳的题真是一道比一道让人自闭...QAQ~~

这道题没什么好的办法，Polya定理也毫无用武之地，只能暴力构造出所有可能的连通块，然后用set判重，比较考验基本功。

连通块可以用一个结构体D来表示，D的n代表黑块数量，然后有至多10个点P(x,y)，用另一个结构体数组P[N]来表示。

问题的关键在于如何判重。

首先要知道set是通过<运算符来判重的，因此肯定要重载一下<运算符。既然要重载<运算符，那么就需要能比较出两个连通块的大小来。

如何比较两个黑块数量相同的连通块的大小呢？可以类比向量的字典序大小比较法，把所有的黑块按照x从小到大排序，x相同的按y从小到大排序，就可以比较大小了。

但是同构的两个连通块之间是不具有大小关系的，因此要先想办法把同构的连通块弄成统一的样子。

考虑三类等价变换：

1.平移：$(x,y)\leftrightarrow(x+a,y+b)$

2.旋转：$(x,y)\leftrightarrow(-y,x)$

3.翻转：$(x,y)\leftrightarrow(-x,y)$

所有同构的连通块都可以通过以上三类变换相互得到，对于同构的连通块，可以只保留其中字典序最小的。由于通过旋转和翻转能构造出的不同连通块只有8种，因此可以枚举这8中连通块，然后平移到左上角，取其中字典序最小的即可。

注意在比较字典序的时候，正反都要比较一下。（某人因为忘了反着比较而花了两个小时写了一整页代码来debug~~）

然后就没什么特别需要注意的了，设st[i][j][k]为用i个黑块能构造出j*k(j<=k)的异构连通块的集合，递推搞一搞就行了。

代码：（七重for循环，大概是我写过的层数最多的for循环了~~UVA的评测机也很给力，本地要跑300+ms，交上去30ms就过了）

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=+,inf=0x3f3f3f3f;

 const int dx[]= {,,-,};

 const int dy[]= {-,,,};

 //格点

 struct P {

     int x,y;

     bool operator==(const P& b)const {return x==b.x&&y==b.y;}

     bool operator<(const P& b)const {return x!=b.x?x<b.x:y<b.y;}

 };

 //连通块

 struct D {

     int n;

     P p[N];

     D(int _n):n(_n) {}

     //字典序比较，重点

     bool operator<(const D& b)const {

         for(int i=; i<n; ++i) {

             if(p[i]<b.p[i])return ;

             if(b.p[i]<p[i])return ;

         }

         return ;

     }

     //旋转

     D rot() {

         D ret(n);

         for(int i=; i<n; ++i)ret.p[i]= {-p[i].y,p[i].x};

         return ret;

     }

     //翻转

     D flip() {

         D ret(n);

         for(int i=; i<n; ++i)ret.p[i]= {-p[i].x,p[i].y};

         return ret;

     }

     //平移到左上角

     D norm() {

         D ret=*this;

         int dx=inf,dy=inf;

         for(int i=; i<n; ++i)dx=min(dx,ret.p[i].x),dy=min(dy,ret.p[i].y);

         for(int i=; i<n; ++i)ret.p[i].x-=dx,ret.p[i].y-=dy;

         sort(ret.p,ret.p+n);

         return ret;

     }

     //字典序最小的同构

     D minimum() {

         D a=this->norm(),b=a;

         for(int i=; i<; ++i,b=b.flip())

             for(int j=; j<; ++j,b=b.rot()) {

                 b=b.norm();

                 if(b<a)a=b;

             }

         return a;

     }

 };

 set<D> st[N][N][N];

 int n,w,h,ans;

 int main() {

     D t();

     t.p[]= {,};

     st[][][].insert(t);

     for(int _=; _<; ++_) {

         for(int i=; i<=; ++i)

             for(int j=i; j<=; ++j) {

                 for(D t:st[_][i][j]) {

                     t.n++;

                     for(int k=; k<t.n-; ++k) {

                         for(int f=; f<; ++f) {

                             t.p[t.n-]= {t.p[k].x+dx[f],t.p[k].y+dy[f]};

                             bool ff=;

                             for(int l=; l<t.n-; ++l)if(t.p[t.n-]==t.p[l]) {ff=; break;}//防止格点重复

                             if(!ff)continue;

                             int maxx=~inf,minx=inf,maxy=~inf,miny=inf;

                             for(int l=; l<t.n; ++l) {

                                 maxx=max(maxx,t.p[l].x);

                                 minx=min(minx,t.p[l].x);

                                 maxy=max(maxy,t.p[l].y);

                                 miny=min(miny,t.p[l].y);

                             }

                             int tx=maxx-minx+,ty=maxy-miny+;

                             if(tx>ty)swap(tx,ty);

                             st[_+][tx][ty].insert(t.minimum());

                         }

                     }

                 }

             }

     }

     while(scanf("%d%d%d",&n,&w,&h)==) {

         ans=;

         if(w>h)swap(w,h);

         for(int i=; i<=w; ++i)

             for(int j=; j<=h; ++j)

                 ans+=st[n][i][j].size();

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

UVA - 1602 Lattice Animals (暴力+同构判定)

最新文章

热门文章