例题 7-14 网格动物（Lattice Animals, ACM/ICPC NEERC 2004, UVa1602）

本文主要是介绍例题 7-14 网格动物（Lattice Animals, ACM/ICPC NEERC 2004, UVa1602），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-1602
分类：数据结构,好题
备注：生成n连块，考验思维，打表

代码与其它博客一样，似乎起源都是lrj老师。
很神奇，也很好理解，翻转旋转很容易想到，平移依靠坐标的相对位置就感觉很奇妙。然后每次增块都是基于上一次的图形的。对set的应用也很巧妙。
因为从(0,0)开始增块，因此当前连块的长宽就取最大的x,y再加一即可。

#include<bits/stdc++.h>
using namespace std;struct Cell{int x,y;Cell(int _x=0,int _y=0):x(_x),y(_y){}bool operator < (const Cell &rhs) const{return x<rhs.x||(x==rhs.x&&y<rhs.y);}
};typedef set<Cell> Polyomino;inline Polyomino normalize(const Polyomino &p){Polyomino q;int minX=p.begin()->x, minY=p.begin()->y;for(Polyomino::iterator it=p.begin();it!=p.end();++it){minX=min(minX,it->x);minY=min(minY,it->y);}for(Polyomino::iterator it=p.begin();it!=p.end();++it){q.insert(Cell(it->x-minX,it->y-minY));}return q;
}inline Polyomino rotate(const Polyomino &p){//坐标轴逆时针旋转90度Polyomino q;for(Polyomino::iterator it=p.begin();it!=p.end();++it){q.insert(Cell(it->y,-it->x));}return normalize(q);
}inline Polyomino flip(const Polyomino &p){//以y轴为对称轴翻转Polyomino q;for(Polyomino::iterator it=p.begin();it!=p.end();++it){q.insert(Cell(-it->x,it->y));}return normalize(q);
}const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const int maxn=11;
set<Polyomino> Poly[maxn];
int ans[maxn][maxn][maxn];inline bool flipInFourDir(Polyomino &p, int n){for(int i=0;i<4;++i){if(Poly[n].count(p))return false;p=rotate(p);}return true;
}void checkPolyomino(const Polyomino &src, const Cell &newCell){Polyomino q=src;q.insert(newCell);q=normalize(q);int n=q.size();if(flipInFourDir(q,n)==false)return;q=flip(q);if(flipInFourDir(q,n)==false)return;Poly[n].insert(q);
}void init(){Polyomino p;p.insert(Cell(0,0));Poly[1].insert(p);for(int n=2;n<maxn;++n){for(set<Polyomino>::iterator it=Poly[n-1].begin();it!=Poly[n-1].end();++it){for(Polyomino::const_iterator it2=(*it).begin();it2!=(*it).end();++it2){for(int i=0;i<4;++i){Cell newCell(it2->x+dir[i][0],it2->y+dir[i][1]);if((*it).count(newCell)==0)checkPolyomino(*it,newCell);}}}}for(int n=1;n<maxn;++n){for(int w=1;w<maxn;++w){for(int h=1;h<maxn;++h){int cnt=0;//找到长和宽符合要求的for(set<Polyomino>::iterator it=Poly[n].begin();it!=Poly[n].end();++it){int maxX=0,maxY=0;for(Polyomino::iterator it2=it->begin();it2!=it->end();++it2){maxX=max(maxX,it2->x);maxY=max(maxY,it2->y);}if(max(w,h)>max(maxX,maxY)&&min(w,h)>min(maxX,maxY))++cnt;}ans[n][w][h]=cnt;}}}
}int main(void){//freopen("in.txt","r",stdin);init();int n,w,h;while (~scanf("%d %d %d",&n,&w,&h)){printf("%d\n",ans[n][w][h]);}return 0;
}