https://vjudge.net/problem/UVA-1602

?

題意：w*h網格里放n連塊，問有多少種放法

翻轉、旋轉90°、平移之后相同的算一種

?

推薦題解：

http://blog.csdn.net/qq_29169749/article/details/51420013

?

解決本題的三個問題：

1、狀態的有效表示

2、狀態的搜索

3、狀態的判重

?

1、狀態表示：set套set

定義結構體類型Cell 表示每一個格子的坐標

set<Cell>polyomino 表示一個合法的連通塊 坐標 集合

set<polyomino>sp[i] ?表示所有的i連塊集合

這樣用set里帶的count（） 可以方便的判重

?

2、每一個n連塊都可以有一個n-1連塊增加一個而來

?

3、

平移：

將連通塊標準化，即連通塊里坐標最小的格子（minx，miny）映射到（0,0）上去，

然后連通塊整體沿向量（minx，miny）方向平移

稱之為標準化

標準化之后的連通塊相同，則他們可以通過平移操作相同

旋轉：

現將連通塊標準化

然后每次旋轉90°，即坐標由（x，y）變為（y，-x）

然后再標準化

翻轉：

先將連通塊標準化

然后沿x軸翻轉，即坐標由（x，y）變為 （x，-y）

然后再標準化

?

翻轉時只需沿x軸翻轉

因為沿y軸翻轉可以看做 先沿x軸翻轉，再旋轉2次90°

對于每一種翻轉、旋轉、翻轉之后再旋轉、旋轉之后再翻轉

均可以有旋轉和翻轉的組合完成

?

所以判重的時候，先判平移

然后 旋轉4次90°

然后沿x軸翻轉，再旋轉4次90°

?

#include<set> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm>using namespace std;int ans[11][11][11];struct Cell {int x,y;Cell(int x=0,int y=0):x(x),y(y) { }bool operator < (const Cell & rhs) const{if(x!=rhs.x) return x<rhs.x;return y<rhs.y; } }; typedef set<Cell> polyomino; set<polyomino> sp[11];const int dir_x[]={-1,1,0,0}; const int dir_y[]={0,0,-1,1};inline polyomino normalize(const polyomino &p) {int minx=p.begin()->x,miny=p.begin()->y;for(polyomino :: const_iterator it=p.begin();it!=p.end();it++){minx=min(minx,it->x);miny=min(miny,it->y);}polyomino tmp;for(polyomino :: const_iterator it=p.begin();it!=p.end();it++){int x=it->x,y=it->y;tmp.insert(Cell(x-minx,y-miny));}return tmp; }inline polyomino rotation(const polyomino &p) {polyomino tmp;for(polyomino :: const_iterator it=p.begin();it!=p.end();it++){int x=it->x,y=it->y;tmp.insert(Cell(y,-x));}return normalize(tmp); }inline polyomino flip_x(const polyomino &p) {polyomino tmp;for(polyomino :: const_iterator it=p.begin();it!=p.end();it++){int x=it->x,y=it->y;tmp.insert(Cell(x,-y));}return normalize(tmp);} void set_poly(const polyomino & p,const Cell &c) {polyomino tmp=p;tmp.insert(c);tmp=normalize(tmp);int n=tmp.size();for(int i=0;i<4;i++){if(sp[n].count(tmp)) return;tmp=rotation(tmp);} tmp=flip_x(tmp);for(int i=0;i<4;i++){if(sp[n].count(tmp)) return;tmp=rotation(tmp);}sp[n].insert(tmp); }void make_Ans_List() {polyomino cur;cur.insert(Cell(0,0));sp[1].insert(cur);for(int n=1;n<=10;n++)for(set<polyomino>::iterator it=sp[n-1].begin();it!=sp[n-1].end();it++)for(polyomino ::const_iterator cit=(*it).begin();cit!=(*it).end();cit++)for(int dir=0;dir<4;dir++){Cell newc(cit->x+dir_x[dir],cit->y+dir_y[dir]);if((it->count(newc))==0) set_poly(*it,newc);}for(int n=1;n<=10;n++)for(int w=1;w<=10;w++)for(int h=1;h<=10;h++){int cnt=0;for(set<polyomino>::iterator it=sp[n].begin();it!=sp[n].end();it++){int maxx=0,maxy=0;for(polyomino :: const_iterator c=(*it).begin();c!=(*it).end();c++){maxx=max(maxx,c->x);maxy=max(maxy,c->y);}if(min(maxx,maxy)<min(w,h) && max(maxx,maxy)<max(w,h)) cnt++;}ans[n][w][h]=cnt;}} int main() {make_Ans_List();int n,w,h;while(scanf("%d%d%d",&n,&w,&h)!=EOF){if(n>w*h) printf("0\n");else printf("%d\n",ans[n][w][h]);} }

?

轉載于:https://www.cnblogs.com/TheRoadToTheGold/p/7668659.html

總結

以上是生活随笔為你收集整理的UVA 1602 Lattice Animals的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。