The Solution Of Uva 1602 Lattice Animals （网格动物）

题目地址

UVa 原地址 VJudge

题目大意

给定一个 w * h 的 矩阵，在矩阵中找不同连通块的个数（旋转，翻转，平移算作一种）

题目做法

判重

编码

判重无疑是这道题的重点。那么从判重的方法来看，有两种方法：

STL 的 set手写 hash

从时间来看，set 所消耗的时间肯定更多，但是更加的方便。那么用 hash 来做的话，时间可以保证，但是实现起来略显复杂。 这里重点说一下 hash 的做法。由于 n 是在 10 以内的，且网格最大也是 10*10 的。那么如果我们记录一个格子到另外一个格子的相对位移，数字的范围肯定是在 0~9 以内的。相邻两个格子有两个数字，那么就可以用一个 18 位的数字来表示一个状态。就可以用这个方法来判重。对于一种连通块的一种姿态，如果按照坐标的顺序进行排序，那么我们得到的相对位移的编码肯定是一样的（平移都是同时加坐标值，大小顺序不改变），所以这个方法一定是正确的。

旋转、翻转、平移

90° 旋转就是 x 坐标换为原来的 y 坐标的相反数，y 坐标换成原来的 x 坐标 180° 旋转就是 x 坐标和 y 坐标全相反 270° 旋转就是 x 坐标换为原来的 y 坐标，y 坐标换成原来的 x 坐标的相反数 翻转就是 y 坐标相反 或者 x 坐标相反 在我这种判重方法下，不需要平移就可以判定（计算的是相对位移），但是可以用下面这段代码将序列平移到左上角

void normalize(Point p0[], int n) { sort(p0 + 1, p0 + 1 + n); int xmn = MAXN, ymn = MAXN; for(int i = 1; i <= n; ++i) { xmn = min(xmn, p0[i].x); ymn = min(ymn, p0[i].y); } for(int i = 1; i <= n; ++i) { p0[i].x -= xmn; p0[i].y -= ymn; } }

进行上面这几种操作后，用 encode 函数获取对应的编码，只要其中有一个编码出现过，就说明这个排列已经出现过，反之就没有出现过，将其中任意一个编码加入 hash 表即可。

构造

方案一（超时）

既然题目要求构造连通块，那么我们就用 dfs 来构造连通块。在 dfs 中，我们可以找到一个已经存在的点，向它的四周进行扩展，这样可以构造出连通块。 这样的方法是在线的，枚举量很大，容易超时。

方案二

构造有 i 个连通块的方案时，我们可以通过有 i - 1 个连通块的方案来推出有 i 个连通块的方案（如方案一中的扩展），那么我们可以把这些方案储存下来，打一个三维表 ans[n][w][h] 表示在 w * h 的网格中构造 n 连通块的方案总数，那么我们只需要看我们构造出来的解是否符合 w 和 h 的限定就可以了。具体的方法是取 max(x)、min(x)、max(y)、min(y)，然后看 max(max(x) - min(x), max(y) - min(y)) <= max(w, h) && min(max(x) - min(x), max(y) - min(y)) <= min(w, h) 就可以了。如果保存方案的时候进行了坐标的平移，那么可以直接看 max(x) 和 max(y) 是否在 x 和 y 的范围以内。 具体请看代码。

代码

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define MAXN 10 #define HASHSIZE 100007LL typedef long long int64; int n, w, h, ans[MAXN + 5][MAXN + 5][MAXN + 5]; int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; bool in_map(int x, int y) { return x >= 1 && x <= h && y >= 1 && y <= w; } struct Point { int x, y; bool operator < (const Point& rhs) const { return x < rhs.x || (x == rhs.x && y < rhs.y); } bool operator == (const Point& rhs) const { return x == rhs.x && y == rhs.y; } }; struct hashNode { hashNode* next; int64 code; } *hashHead[HASHSIZE + 5], hashEdge[100000], *hashEcnt = hashEdge; void normalize(Point p0[], int n) { //平移至左上角 sort(p0 + 1, p0 + 1 + n); int xmn = MAXN, ymn = MAXN; for(int i = 1; i <= n; ++i) { xmn = min(xmn, p0[i].x); ymn = min(ymn, p0[i].y); } for(int i = 1; i <= n; ++i) { p0[i].x -= xmn; p0[i].y -= ymn; } } void rotate90(Point p0[], int n) { //旋转90度 Point p[MAXN + 5]; for(int i = 1; i <= n; ++i) { p[i].x = -p0[i].y; p[i].y = p0[i].x; } normalize(p, n); memcpy(p0, p, sizeof p); } void rotate180(Point p0[], int n) { //旋转180度 Point p[MAXN + 5]; for(int i = 1; i <= n; ++i) { p[i].x = -p0[i].x; p[i].y = -p0[i].y; } normalize(p, n); memcpy(p0, p, sizeof p); } void rotate270(Point p0[], int n) { //旋转270度 Point p[MAXN + 5]; for(int i = 1; i <= n; ++i) { p[i].x = p0[i].y; p[i].y = -p0[i].x; } normalize(p, n); memcpy(p0, p, sizeof p); } void upside_down(Point p0[], int n) { //上下翻转（上下或者左右都可以） Point p[MAXN + 5]; for(int i = 1; i <= n; ++i) { p[i].x = p0[i].x; p[i].y = -p0[i].y; } normalize(p, n); memcpy(p0, p, sizeof p); } int64 encode(Point p[], int n) { // 编码 int64 code = 0; for(int i = 2; i <= n; ++i) { int ox = p[i].x - p[i - 1].x; int oy = p[i].y - p[i - 1].y; code = code * 100 + ox * 10 + oy; } if(code < 0) printf(" "); return code; } bool check_in_hash(int64 code) { // 检查 hash 表中是否已经存在这个 code int h = code % HASHSIZE; for(hashNode* p = hashHead[h]; p != NULL; p = p->next) if(p->code == code) return true; return false; } bool try_to_insert(Point p[], int n) { // 判重并插入 Point p0[MAXN + 5], rp0[MAXN + 5]; int64 code; memcpy(p0, p, sizeof(Point)*(MAXN + 5)); normalize(p, n); code = encode(p0, n); if(check_in_hash(code)) return false; memcpy(p0, p, sizeof(Point)*(MAXN + 5)); rotate90(p0, n); code = encode(p0, n); if(check_in_hash(code)) return false; memcpy(p0, p, sizeof(Point)*(MAXN + 5)); rotate180(p0, n); code = encode(p0, n); if(check_in_hash(code)) return false; memcpy(p0, p, sizeof(Point)*(MAXN + 5)); rotate270(p0, n); code = encode(p0, n); if(check_in_hash(code)) return false; memcpy(rp0, p, sizeof(Point)*(MAXN + 5)); upside_down(rp0, n); code = encode(rp0, n); if(check_in_hash(code)) return false; memcpy(p0, rp0, sizeof rp0); rotate90(p0, n); code = encode(p0, n); if(check_in_hash(code)) return false; memcpy(p0, rp0, sizeof rp0); rotate180(p0, n); code = encode(p0, n); if(check_in_hash(code)) return false; memcpy(p0, rp0, sizeof rp0); rotate270(p0, n); code = encode(p0, n); if(check_in_hash(code)) return false; int h = code % HASHSIZE; hashNode* hn = hashEcnt; hn->next = hashHead[h]; hn->code = code; hashHead[h] = hn; ++hashEcnt; return true; } bool find(Point p0[], Point p, int n) { // 二分查找看我们想要加入的 p 是否已经存在在这个连通块中，p0 是已经排过序的 int pos = lower_bound(p0 + 1, p0 + 1 + n, p) - (p0 + 1) + 1; if(pos == n + 1) return false; if(p0[pos] == p) return true; return false; } struct Poly { int cnt; Point p[4655 + 5][MAXN + 5]; } poly[MAXN + 5]; void getans() { poly[1].cnt = 1; poly[1].p[1][1] = (Point) { 0, 0 }; //1 连通块 for(int i = 2; i <= MAXN; ++i) { int& cnt = poly[i].cnt; for(int j = 1; j <= poly[i - 1].cnt; ++j) //枚举上一层连通块 for(int k = 1; k <= i - 1; ++k) //枚举每个点 for(int q = 0; q < 4; ++q) { //四个方向扩展 Point p = (Point) { poly[i - 1].p[j][k].x + dir[q][0], poly[i - 1].p[j][k].y + dir[q][1] }; if(!find(poly[i - 1].p[j], p, i - 1)) { //检查是否已经存在这个店 Point pp[MAXN + 5]; memcpy(pp, poly[i - 1].p[j], sizeof poly[i - 1].p[j]); pp[i] = p; normalize(pp, i); if(try_to_insert(pp, i)) //尝试插入 memcpy(poly[i].p[++cnt], pp, sizeof pp); //储存连通块 } } } for(int n = 1; n <= MAXN; ++n) for(int w = 1; w <= n; ++w) for(int h = 1; h <= n; ++h) { int cnt = 0; for(int i = 1; i <= poly[n].cnt; ++i) { //我这里 normalize 过，所以直接看 max(x) 和 max(y) int xmx = 0, ymx = 0; for(int j = 1; j <= n; ++j) { xmx = max(xmx, poly[n].p[i][j].x); ymx = max(ymx, poly[n].p[i][j].y); } if(min(xmx, ymx) < min(h, w) && max(xmx, ymx) < max(h, w)) ++cnt; } ans[n][w][h] = cnt; } } int main() { getans(); while(scanf("%d%d%d", &n, &w, &h) != EOF) { printf("%d\n", ans[n][w][h]); } }