【POJ】2170 Lattice Animals

1. 题目描述
给定$n imes m， n、m in [1, 10]$的方格，求不同形状的$[1 cdots 10]$联通块的个数？
所谓不同形状，表示不能通过平移、旋转、镜像实现相同的形状。

2. 基本思路
显然数据不大，那么可以打表。首先考虑，这个表怎么打？不妨使用$cn$表示连通块数。
那么对于$n imes m, m、n ge cn$的种类数与$cn imes cn$中$cn$连通块数完全相同。
否则搜索$cn imes cn$中$cn$中的连通块，找出那些在边界$n imes m$的数量即可。
那么，关键问题是怎么对连通块抽象，怎么进行状态压缩。显然存在着平移、旋转、镜像等操作。
这也意味着同一个连通块的表达形式可能不同。
这里采用正则化的思想，即找到$x,y$的最小值，然后对所有坐标减去这个值。然后在对坐标值排序。
即可以得到标准化的连通块。那么如何状态压缩呢？
对排好序的连通块的$x,y$进行压缩，因此pair<int,int>即可以表示一个连通块，使用map充当visit。
假定我们已经得到了$cn imes cn$中$n-1$连通的情况，那么对其中的每个块向四个方向拓展既可以得到所有$n$连通的情况。
这里，首先注意边界范围不能超过$cn imes cn$，同时，仅考虑镜像和旋转得到的状态visit中是否包含。
平移不用考虑是因为使用了正则化，大大减少了计算量。

3. 代码
(1) 打表代码，其实不打表也能过

  1 /* 2170 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <bitset>
 12 #include <algorithm>
 13 #include <cstdio>
 14 #include <cmath>
 15 #include <ctime>
 16 #include <cstring>
 17 #include <climits>
 18 #include <cctype>
 19 #include <cassert>
 20 #include <functional>
 21 #include <iterator>
 22 #include <iomanip>
 23 using namespace std;
 24 //#pragma comment(linker,"/STACK:102400000,1024000")
 25 
 26 #define sti                set<int>
 27 #define stpii            set<pair<int, int> >
 28 #define mpii            map<int,int>
 29 #define vi                vector<int>
 30 #define pii                pair<int,int>
 31 #define vpii            vector<pair<int,int> >
 32 #define rep(i, a, n)     for (int i=a;i<n;++i)
 33 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 34 #define clr                clear
 35 #define pb                 push_back
 36 #define mp                 make_pair
 37 #define fir                first
 38 #define sec                second
 39 #define all(x)             (x).begin(),(x).end()
 40 #define SZ(x)             ((int)(x).size())
 41 #define lson            l, mid, rt<<1
 42 #define rson            mid+1, r, rt<<1|1
 43 #define INF                0x3f3f3f3f
 44 #define mset(a, val)    memset(a, (val), sizeof(a))
 45 
 46 #define LL unsigned long long
 47 
 48 typedef struct node_t {
 49     vpii vp;
 50 
 51     void sorted() {
 52         sort(all(vp));
 53     }
 54 
 55     void push_back(pii p) {
 56         vp.pb(p);
 57     }
 58 
 59     void clear() {
 60         vp.clr();
 61     }
 62 
 63     int size() const {
 64         return vp.size();
 65     }
 66     
 67     void regular() {
 68         int mnx = INT_MAX, mny = INT_MAX;
 69         
 70         int sz = SZ(vp);
 71         
 72         rep(i, 0, sz) {
 73             mnx = min(vp[i].fir, mnx);
 74             mny = min(vp[i].sec, mny);
 75         }
 76         
 77         rep(i, 0, sz) {
 78             vp[i].fir -= mnx;
 79             vp[i].sec -= mny;
 80         }
 81     }
 82 
 83     pair<pii,pii> calBound() const {
 84         int mnx, mny, mxx, mxy;
 85         int sz = SZ(vp);
 86 
 87         if (sz == 0)
 88             return mp(mp(0, 0), mp(0,0));
 89 
 90         mnx = mny = INT_MAX;
 91         mxx = mxy = INT_MIN;
 92         rep(i, 0, sz) {
 93             mnx = min(mnx, vp[i].fir);
 94             mxx = max(mxx, vp[i].fir);
 95             mny = min(mny, vp[i].sec);
 96             mxy = max(mxy, vp[i].sec);
 97         }
 98 
 99         return mp(mp(mnx, mxx), mp(mny, mxy));
100     }
101     
102     pii calL() const {
103         pair<pii,pii> ppii = calBound();
104         return mp(ppii.fir.sec-ppii.fir.fir+1, ppii.sec.sec-ppii.sec.fir+1);
105     }
106 } node_t;
107 
108 const int maxn = 11;
109 vector<node_t> E[maxn][maxn];
110 set<pair<LL,LL> > has;
111 int ans[maxn][maxn][maxn];
112 int dir[4][2] = {
113     -1, 0, 1,0, 0,-1, 0,1
114 };
115 int n, m, cn;
116 bool printInfo = false;
117     
118 pair<LL,LL> zip(const node_t& d, int sz) {
119     node_t nd = d;
120     LL x = 0, y = 0;
121     
122     nd.regular();
123     nd.sorted();
124     
125     rep(i, 0, sz)  {
126         x = 10 * x + nd.vp[i].fir;
127         y = 10 * y + nd.vp[i].sec;
128     }
129     
130     return mp(x, y);
131 }
132 
133 void unzip(pair<LL,LL> p, node_t& nd, int sz) {
134     LL &x = p.fir, &y = p.sec;
135     
136     per(i, 0, sz) {
137         nd.vp[i].fir = x % 10;
138         nd.vp[i].sec = y % 10;
139         x /= 10;
140         y /= 10;
141     }
142 }
143 
144 bool check(const node_t& b) {
145     pair<LL,LL> p = zip(b, cn);
146 
147     return has.find(p) != has.end();
148 }
149 
150 void rotate(node_t& d) {
151     rep(i, 0, cn) {
152         swap(d.vp[i].fir, d.vp[i].sec);
153         d.vp[i].sec = -d.vp[i].sec;
154     }
155 }
156 
157 void mirror(node_t& d) {
158     rep(i, 0, cn)
159         d.vp[i].fir = -d.vp[i].fir;
160 }
161 
162 bool judge(node_t& d) {
163     rep(i, 0, cn) {
164         rep(j, i+1, cn) {
165             if (d.vp[i] == d.vp[j])
166                 return false;
167         }
168     }
169     
170     node_t dd;
171     
172     dd = d;
173     
174     rep(i, 0, 2) {
175         rep(j, 0, 4) {
176             if (check(dd))
177                 return false;
178             rotate(dd);
179         }
180         mirror(dd);
181     }
182 
183     return true;
184 }
185 
186 int calc() {
187     if (n>=cn && m>=cn)
188         return SZ(E[cn][cn]);
189 
190     const vector<node_t>& vc = E[cn][cn];
191     int sz = SZ(vc);
192     int ret = 0;
193 
194     rep(i, 0, sz) {
195         pair<pii,pii> ppii = vc[i].calBound();
196         int lx = ppii.fir.sec - ppii.fir.fir + 1;
197         int ly = ppii.sec.sec - ppii.sec.fir + 1;
198         if ((lx<=n && ly<=m) || (lx<=m && ly<=n))
199             ++ret;
200     }
201 
202     return ret;
203 }
204 
205 void printAns() {
206     puts("int ans[10][100] = {");
207     rep(i, 1, 11) {
208         putchar('	');
209         putchar('{');
210         rep(j, 1, 11) {
211             rep(k, 1, 11) {
212                 if (j==1 && k==1)
213                     printf("%d", ans[i][j][k]);
214                 else
215                     printf(",%d", ans[i][j][k]);
216             }
217         }
218         putchar('}');
219         if (i != 10)
220             putchar(',');
221         putchar('
');
222     }
223     puts("};");
224 }
225 
226 void solve() {
227     vector<node_t>& vc = E[n][cn];
228     const vector<node_t>& ovc = E[n][cn-1];
229 
230     has.clr();
231     int osz = SZ(ovc);
232 
233     rep(i, 0, osz) {
234         const node_t& nd = ovc[i];
235         pair<pii,pii> ppii = nd.calBound();
236         int mxx, mxy, mnx, mny;
237         
238         node_t d;
239 
240         rep(j, 0, cn-1) d.pb(nd.vp[j]);
241         d.pb(mp(0, 0));
242         
243         rep(j, 0, cn-1) {
244             const int& x = nd.vp[j].fir;
245             const int& y = nd.vp[j].sec;
246             int xx, yy;
247 
248             rep(k, 0, 4) {
249                 xx = x + dir[k][0];
250                 yy = y + dir[k][1];
251                 d.vp[cn-1].fir = xx;
252                 d.vp[cn-1].sec = yy;
253                 
254                 mnx = min(ppii.fir.fir, xx);
255                 mxx = max(ppii.fir.sec, xx);
256                 mny = min(ppii.sec.fir, yy);
257                 mxy = max(ppii.sec.sec, yy);
258                 
259                 if (mxx-mnx+1>n || mxy-mny+1>n)
260                     continue;
261                 
262                 if (judge(d)) {
263                     vc.pb(d);
264                     pair<LL, LL> p = zip(d, cn);
265                     has.insert(p);
266                 }
267             }
268         }
269     }
270 }
271 
272 void init() {
273     for (n=1; n<maxn; ++n) {
274         for (cn=1; cn<maxn; ++cn) {
275             if (cn == 1) {
276                 node_t nd;
277                 nd.pb(mp(0, 0));
278                 E[n][cn].pb(nd);
279             } else if (cn < n) {
280                 int sz = SZ(E[cn][cn]);
281                 rep(i, 0, sz)
282                     E[n][cn].pb(E[cn][cn][i]);
283             } else {
284                 solve();
285             }
286             
287             printf("E[%d][%d] = %d
", n, cn, SZ(E[n][cn]));
288             fflush(stdout);
289         }
290     }
291 
292     for (cn=1; cn<=10; ++cn) {
293         for (n=1; n<=cn; ++n) {
294             for (m=n; m<=cn; ++m) {
295                 ans[cn][n][m] = ans[cn][m][n] = calc();
296             }
297         }
298     }
299 
300     printAns();
301 }
302 
303 int main() {
304     ios::sync_with_stdio(false);
305     #ifndef ONLINE_JUDGE
306         freopen("data.in", "r", stdin);
307         freopen("data.out", "w", stdout);
308     #endif
309 
310     init();
311 
312     #ifndef ONLINE_JUDGE
313         printf("time = %d.
", (int)clock());
314     #endif
315 
316     return 0;
317 }

(2) AC程序

 1 /* 2170 */
 2 #include <iostream>
 3 #include <sstream>
 4 #include <string>
 5 #include <map>
 6 #include <queue>
 7 #include <set>
 8 #include <stack>
 9 #include <vector>
10 #include <deque>
11 #include <bitset>
12 #include <algorithm>
13 #include <cstdio>
14 #include <cmath>
15 #include <ctime>
16 #include <cstring>
17 #include <climits>
18 #include <cctype>
19 #include <cassert>
20 #include <functional>
21 #include <iterator>
22 #include <iomanip>
23 using namespace std;
24 //#pragma comment(linker,"/STACK:102400000,1024000")
25 
26 #define sti                set<int>
27 #define stpii            set<pair<int, int> >
28 #define mpii            map<int,int>
29 #define vi                vector<int>
30 #define pii                pair<int,int>
31 #define vpii            vector<pair<int,int> >
32 #define rep(i, a, n)     for (int i=a;i<n;++i)
33 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
34 #define clr                clear
35 #define pb                 push_back
36 #define mp                 make_pair
37 #define fir                first
38 #define sec                second
39 #define all(x)             (x).begin(),(x).end()
40 #define SZ(x)             ((int)(x).size())
41 #define lson            l, mid, rt<<1
42 #define rson            mid+1, r, rt<<1|1
43 #define INF                0x3f3f3f3f
44 #define mset(a, val)    memset(a, (val), sizeof(a))
45 
46 int ans[10][100] = {
47     {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
48     {0,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
49     {0,0,1,0,0,0,0,0,0,0,0,1,2,0,0,0,0,0,0,0,1,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
50     {0,0,0,1,0,0,0,0,0,0,0,1,4,5,0,0,0,0,0,0,0,4,4,5,0,0,0,0,0,0,1,5,5,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
51     {0,0,0,0,1,0,0,0,0,0,0,0,2,5,6,0,0,0,0,0,0,2,8,11,12,0,0,0,0,0,0,5,11,11,12,0,0,0,0,0,1,6,12,12,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
52     {0,0,0,0,0,1,0,0,0,0,0,0,1,7,12,13,0,0,0,0,0,1,8,29,34,35,0,0,0,0,0,7,29,29,34,35,0,0,0,0,0,12,34,34,34,35,0,0,0,0,1,13,35,35,35,35,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
53     {0,0,0,0,0,0,1,0,0,0,0,0,0,2,13,18,19,0,0,0,0,0,7,48,84,89,90,0,0,0,0,2,48,66,102,107,108,0,0,0,0,13,84,102,102,107,108,0,0,0,0,18,89,107,107,107,108,0,0,0,1,19,90,108,108,108,108,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
54     {0,0,0,0,0,0,0,1,0,0,0,0,0,1,11,30,37,38,0,0,0,0,3,63,169,223,230,231,0,0,0,1,63,140,307,361,368,369,0,0,0,11,169,307,307,361,368,369,0,0,0,30,223,361,361,361,368,369,0,0,0,37,230,368,368,368,368,369,0,0,1,38,231,369,369,369,369,369,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
55     {0,0,0,0,0,0,0,0,1,0,0,0,0,0,3,25,53,60,61,0,0,0,1,43,256,466,543,550,551,0,0,0,43,224,820,1127,1204,1211,1212,0,0,3,256,820,893,1200,1277,1284,1285,0,0,25,466,1127,1200,1200,1277,1284,1285,0,0,53,543,1204,1277,1277,1277,1284,1285,0,0,60,550,1211,1284,1284,1284,1284,1285,0,1,61,551,1212,1285,1285,1285,1285,1285,0,0,0,0,0,0,0,0,0,0,0},
56     {0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,16,68,108,117,118,0,0,0,21,277,842,1226,1329,1338,1339,0,0,21,287,1847,3234,3773,3876,3885,3886,0,1,277,1847,2376,4003,4542,4645,4654,4655,0,16,842,3234,4003,4003,4542,4645,4654,4655,0,68,1226,3773,4542,4542,4542,4645,4654,4655,0,108,1329,3876,4645,4645,4645,4645,4654,4655,0,117,1338,3885,4654,4654,4654,4654,4654,4655,1,118,1339,3886,4655,4655,4655,4655,4655,4655}
57 };
58 
59 int main() {
60     ios::sync_with_stdio(false);
61     #ifndef ONLINE_JUDGE
62         freopen("data.in", "r", stdin);
63         freopen("data.out", "w", stdout);
64     #endif
65 
66     int n, w, h;
67 
68     while (scanf("%d%d%d",&n,&w,&h)!=EOF) {
69         --n;
70         --w;
71         --h;
72         cout << ans[n][w*10+h] << endl;
73     }
74 
75     #ifndef ONLINE_JUDGE
76         printf("time = %d.
", (int)clock());
77     #endif
78 
79     return 0;
80 }

View Code

4. 数据生成器

 1 import sys
 2 import string
 3 from random import randint, shuffle
 4 
 5     
 6 def GenData(fileName):
 7     with open(fileName, "w") as fout:
 8         t = 1
 9         for tt in xrange(t):
10             for j in xrange(1, 11):
11                 for i in xrange(1, j+1):
12                     for k in xrange(1, j+1):
13                         fout.write("%d %d %d
" % (j, i, k))
14             
15             
16 def MovData(srcFileName, desFileName):
17     with open(srcFileName, "r") as fin:
18         lines = fin.readlines()
19     with open(desFileName, "w") as fout:
20         fout.write("".join(lines))
21 
22         
23 def CompData():
24     print "comp"
25     srcFileName = "F:Qt_prjhdojdata.out"
26     desFileName = "F:workspacecpp_hdojdata.out"
27     srcLines = []
28     desLines = []
29     with open(srcFileName, "r") as fin:
30         srcLines = fin.readlines()
31     with open(desFileName, "r") as fin:
32         desLines = fin.readlines()
33     n = min(len(srcLines), len(desLines))-1
34     for i in xrange(n):
35         ans2 = int(desLines[i])
36         ans1 = int(srcLines[i])
37         if ans1 > ans2:
38             print "%d: wrong" % i
39 
40             
41 if __name__ == "__main__":
42     srcFileName = "F:Qt_prjhdojdata.in"
43     desFileName = "F:workspacecpp_hdojdata.in"
44     GenData(srcFileName)
45     MovData(srcFileName, desFileName)

View Code