題目：輸入n，w，h（1n10，1w，hn），求能放在w*h網格里的不同的n連塊的個數（注意：平移、旋轉、翻轉后相同的算作同一種）。

分析：本題關鍵就是如何判重，有n個格子連通，所幸n很小，可以回溯求解，將網格放到坐標系中，旋轉就是將x=y，y=-x，平移就是最小的點與原點距離，然后每個點都減去它，翻轉就是x=x,y=-y，然后再旋轉。所以可以用set來判重。因為取值范圍很小，所以可以打表，將每個大小的網格1*1~10*10都搜索判斷一遍1~10各個連通塊的個數。

#include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<iostream> #include<vector> #include<list> #include<set> using namespace std; int n, w, h; struct cell {int x, y;cell(){}cell(int _x,int _y):x(_x),y(_y){}bool operator<(const cell &u)const {if (x == u.x)return y < u.y;else return x < u.x;} }; int dx[] = { 1,-1,0,0 }; int dy[] = { 0,0,1,-1 }; int ans[15][15][15]; typedef set<cell> poly;//n連通塊 set<poly>blockmp[15];//所有個數的連通塊 inline poly init_norimize(const poly &nlist) {//置原點int minx = 65536, miny = 65536;poly u;for (poly::iterator it = nlist.begin(); it != nlist.end(); ++it) {minx=min(minx, (*it).x);miny=min(miny, (*it).y);}for (poly::iterator it = nlist.begin(); it != nlist.end(); ++it) {u.insert(cell((*it).x - minx, (*it).y-miny));}return u; } inline poly rotate(const poly &nlist) {poly u;for (poly::iterator i = nlist.begin(); i != nlist.end(); i++)u.insert(cell(i->y, -i->x));return init_norimize(u); } inline poly mirror(const poly &nlist) {poly p;for (poly::iterator i = nlist.begin(); i != nlist.end(); i++)p.insert(cell(i->x, -i->y));return init_norimize(p); } bool isexist(poly nlist) {int len = nlist.size();//取得所求連通塊的長度for (int i = 0; i < 4; i++) {nlist = rotate(nlist);if (blockmp[len].count(nlist)) {return true;}}nlist = mirror(nlist);for (int i = 0; i < 4; i++) {nlist = rotate(nlist);if (blockmp[len].count(nlist)) {return true;}}blockmp[len].insert(nlist);return false; } void dfs(const poly &nlist) {if (nlist.size() == n) {isexist(nlist);return;}for(cell it:nlist){for (int i = 0; i < 4; i++) {cell temp(it.x + dx[i], it.y + dy[i]);if (!nlist.count(temp)) {poly t = nlist;t.insert(temp);dfs(t);}}} } void buildtable() {memset(ans, 0, sizeof(ans));poly t;t.insert(cell(0, 0));blockmp[1].insert(t);for (n = 2; n <= 10; n++) {/*for (set<poly>::iterator it = blockmp[n - 1].begin(); it != blockmp[n - 1].end(); ++it) {poly x = *it;dfs(x);}*/for (poly itn : blockmp[n - 1]) //每次都從上一個列舉的塊進行迭代dfs(itn);}for (n = 2; n <= 10; n++) {for (w = 1; w <= 10; w++) {for (h = 1; h <= 10; h++) {int ant = 0;for (poly t1 : blockmp[n]) {int maxx = 0, maxy = 0;for (cell it1 : t1) {maxx = max(maxx, it1.x);maxy = max(maxy, it1.y);}if (min(maxx, maxy) < min(h, w)&&max(maxx,maxy)<max(h,w)) {ant++;}}ans[n][w][h] = ant;}}} } int main() {buildtable();while (scanf("%d%d%d", &n, &w, &h) == 3){if (n == 1) { printf("1\n"); continue; }//1的時候特判printf("%d\n", ans[n][w][h]);}//system("pause");return 0; }

改進：

搜索連通塊用的是回溯，但是因為每次搜索第n連通塊時，都用的是n-1連通塊將它每個格子的周圍添加，實際上，不需要再遞歸，因為加一個正好等于n。

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

完整老師代碼：

#include<cstdio>#include<cstring>#include<algorithm>#include<set>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;#define FOR_CELL(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;FOR_CELL(c, p) {minX = min(minX, c->x);minY = min(minY, c->y);}Polyomino p2; FOR_CELL(c, p)p2.insert(Cell(c->x - minX, c->y - minY));return p2;}inline Polyomino rotate(const Polyomino &p) {Polyomino p2;FOR_CELL(c, p)p2.insert(Cell(c->y, -c->x));return normalize(p2);}inline Polyomino flip(const Polyomino &p) {Polyomino p2;FOR_CELL(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];// add a cell to p0 and check whether it's new. If so, add to the polyonimo setvoid check_polyomino(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);// generatefor(int n = 2; n <= maxn; n++) {for(set<Polyomino>::iterator p = poly[n-1].begin(); p != poly[n-1].end(); ++p)FOR_CELL(c, *p)for(int dir = 0; dir < 4; dir++) {Cell newc(c->x + dx[dir], c->y + dy[dir]);if(p->count(newc) == 0) check_polyomino(*p, newc);}}// precompute answersfor(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;FOR_CELL(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;}

?

總結

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

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