【题解】UVa 1602【Lattice Animals】

分析

这里采用了专用算法Polyomino

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using std::set;using std::max;using std::min;
class Cell{
public:
    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;
#define foreach(c,p) for(Polyomino::const_iterator c = (p).begin();c != (p).end();++c)

inline Polyomino normalize(const Polyomino &p){int minX = p.begin() -> x,minY = p.begin() -> y;foreach(c,p) minX = min(minX,c -> x),minY = min(minY,c -> y);Polyomino p2;foreach(c,p) p2.insert(Cell(c -> x - minX,c -> y - minY));return p2;}
inline Polyomino rotate(const Polyomino &p){Polyomino p2;foreach(c,p) p2.insert(Cell(c -> y,-c -> x));return normalize(p2);}
inline Polyomino flip(const Polyomino &p){Polyomino p2;foreach(c,p) p2.insert(Cell(c -> x,-c -> y));return normalize(p2);}

const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,-1,1};
const int MAXN = 10;

set<Polyomino> poly[MAXN + 1];
int ans[MAXN + 1][MAXN + 1][MAXN + 1];

void checkPolyomino(const Polyomino &p0,const Cell &c){
    Polyomino p = p0;
    p.insert(c);
    p = normalize(p);

    int n = p.size();
    for(int i = 0;i < 4;i++){
        if(poly[n].count(p) != 0) return;
        p = rotate(p);
    }
    p = flip(p);
    for(int i = 0;i < 4;i++){
        if(poly[n].count(p) != 0) return;
        p = rotate(p);
    }
    poly[n].insert(p);
}

void generate(){
    Polyomino s;
    s.insert(Cell(0,0));
    poly[1].insert(s);

    for(int n = 2;n <= MAXN;n++){
        for(set<Polyomino>::iterator p = poly[n - 1].begin();p != poly[n - 1].end();++p)
            foreach(c,*p)
                for(int dir = 0;dir < 4;dir++){
                    Cell newc(c -> x + dx[dir],c -> y + dy[dir]);
                    if(p -> count(newc) == 0) checkPolyomino(*p,newc);
                }
    }

    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 p = poly[n].begin();p != poly[n].end();++p){
                    int maxX = 0,maxY = 0;
                    foreach(c,*p){
                        maxX = max(maxX,c -> x);
                        maxY = max(maxY,c -> y);
                    }
                    if(min(maxX,maxY) < min(h,w) && max(maxX,maxY) < max(h,w)) ++cnt;
                }
                ans[n][w][h] = cnt;
            }
}

int main(){
    generate();
    int n,w,h;
    while(scanf("%d %d %d",&n,&w,&h) == 3) printf("%d\n",ans[n][w][h]);

    return 0;
}