1. 题目描述
给定$n \times m， n、m \in [1, 10]$的方格，求不同形状的$[1 \cdots 10]$联通块的个数？
所谓不同形状，表示不能通过平移、旋转、镜像实现相同的形状。
2. 基本思路
显然数据不大， 那么可以打表。首先考虑，这个表怎么打？不妨使用$cn$表示连通块数。
那么对于$n \times m, m、n \ge cn$的种类数与$cn \times cn$中$cn$连通块数完全相同。
否则搜索$cn \times cn$中$cn$中的连通块，找出那些在边界$n \times m$的数量即可。
那么，关键问题是怎么对连通块抽象，怎么进行状态压缩。显然存在着平移、旋转、镜像等操作。
这也意味着同一个连通块的表达形式可能不同。
这里采用正则化的思想，即找到$x,y$的最小值，然后对所有坐标减去这个值。然后在对坐标值排序。
即可以得到标准化的连通块。那么如何状态压缩呢？
对排好序的连通块的$x,y$进行压缩，因此pair<int,int>即可以表示一个连通块，使用map充当visit。
假定我们已经得到了$cn \times cn$中$n-1$连通的情况，那么对其中的每个块向四个方向拓展既可以得到所有$n$连通的情况。
这里，首先注意边界范围不能超过$cn \times cn$，同时，仅考虑镜像和旋转得到的状态visit中是否包含。
平移不用考虑是因为使用了正则化，大大减少了计算量。
3. 代码
(1) 打表代码，其实不打表也能过
/* 2170 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
#define INF 0x3f3f3f3f
#define mset(a, val) memset(a, (val), sizeof(a)) #define LL unsigned long long typedef struct node_t {
vpii vp; void sorted() {
sort(all(vp));
} void push_back(pii p) {
vp.pb(p);
} void clear() {
vp.clr();
} int size() const {
return vp.size();
} void regular() {
int mnx = INT_MAX, mny = INT_MAX; int sz = SZ(vp); rep(i, , sz) {
mnx = min(vp[i].fir, mnx);
mny = min(vp[i].sec, mny);
} rep(i, , sz) {
vp[i].fir -= mnx;
vp[i].sec -= mny;
}
} pair<pii,pii> calBound() const {
int mnx, mny, mxx, mxy;
int sz = SZ(vp); if (sz == )
return mp(mp(, ), mp(,)); mnx = mny = INT_MAX;
mxx = mxy = INT_MIN;
rep(i, , sz) {
mnx = min(mnx, vp[i].fir);
mxx = max(mxx, vp[i].fir);
mny = min(mny, vp[i].sec);
mxy = max(mxy, vp[i].sec);
} return mp(mp(mnx, mxx), mp(mny, mxy));
} pii calL() const {
pair<pii,pii> ppii = calBound();
return mp(ppii.fir.sec-ppii.fir.fir+, ppii.sec.sec-ppii.sec.fir+);
}
} node_t; const int maxn = ;
vector<node_t> E[maxn][maxn];
set<pair<LL,LL> > has;
int ans[maxn][maxn][maxn];
int dir[][] = {
-, , ,, ,-, ,
};
int n, m, cn;
bool printInfo = false; pair<LL,LL> zip(const node_t& d, int sz) {
node_t nd = d;
LL x = , y = ; nd.regular();
nd.sorted(); rep(i, , sz) {
x = * x + nd.vp[i].fir;
y = * y + nd.vp[i].sec;
} return mp(x, y);
} void unzip(pair<LL,LL> p, node_t& nd, int sz) {
LL &x = p.fir, &y = p.sec; per(i, , sz) {
nd.vp[i].fir = x % ;
nd.vp[i].sec = y % ;
x /= ;
y /= ;
}
} bool check(const node_t& b) {
pair<LL,LL> p = zip(b, cn); return has.find(p) != has.end();
} void rotate(node_t& d) {
rep(i, , cn) {
swap(d.vp[i].fir, d.vp[i].sec);
d.vp[i].sec = -d.vp[i].sec;
}
} void mirror(node_t& d) {
rep(i, , cn)
d.vp[i].fir = -d.vp[i].fir;
} bool judge(node_t& d) {
rep(i, , cn) {
rep(j, i+, cn) {
if (d.vp[i] == d.vp[j])
return false;
}
} node_t dd; dd = d; rep(i, , ) {
rep(j, , ) {
if (check(dd))
return false;
rotate(dd);
}
mirror(dd);
} return true;
} int calc() {
if (n>=cn && m>=cn)
return SZ(E[cn][cn]); const vector<node_t>& vc = E[cn][cn];
int sz = SZ(vc);
int ret = ; rep(i, , sz) {
pair<pii,pii> ppii = vc[i].calBound();
int lx = ppii.fir.sec - ppii.fir.fir + ;
int ly = ppii.sec.sec - ppii.sec.fir + ;
if ((lx<=n && ly<=m) || (lx<=m && ly<=n))
++ret;
} return ret;
} void printAns() {
puts("int ans[10][100] = {");
rep(i, , ) {
putchar('\t');
putchar('{');
rep(j, , ) {
rep(k, , ) {
if (j== && k==)
printf("%d", ans[i][j][k]);
else
printf(",%d", ans[i][j][k]);
}
}
putchar('}');
if (i != )
putchar(',');
putchar('\n');
}
puts("};");
} void solve() {
vector<node_t>& vc = E[n][cn];
const vector<node_t>& ovc = E[n][cn-]; has.clr();
int osz = SZ(ovc); rep(i, , osz) {
const node_t& nd = ovc[i];
pair<pii,pii> ppii = nd.calBound();
int mxx, mxy, mnx, mny; node_t d; rep(j, , cn-) d.pb(nd.vp[j]);
d.pb(mp(, )); rep(j, , cn-) {
const int& x = nd.vp[j].fir;
const int& y = nd.vp[j].sec;
int xx, yy; rep(k, , ) {
xx = x + dir[k][];
yy = y + dir[k][];
d.vp[cn-].fir = xx;
d.vp[cn-].sec = yy; mnx = min(ppii.fir.fir, xx);
mxx = max(ppii.fir.sec, xx);
mny = min(ppii.sec.fir, yy);
mxy = max(ppii.sec.sec, yy); if (mxx-mnx+>n || mxy-mny+>n)
continue; if (judge(d)) {
vc.pb(d);
pair<LL, LL> p = zip(d, cn);
has.insert(p);
}
}
}
}
} void init() {
for (n=; n<maxn; ++n) {
for (cn=; cn<maxn; ++cn) {
if (cn == ) {
node_t nd;
nd.pb(mp(, ));
E[n][cn].pb(nd);
} else if (cn < n) {
int sz = SZ(E[cn][cn]);
rep(i, , sz)
E[n][cn].pb(E[cn][cn][i]);
} else {
solve();
} printf("E[%d][%d] = %d\n", n, cn, SZ(E[n][cn]));
fflush(stdout);
}
} for (cn=; cn<=; ++cn) {
for (n=; n<=cn; ++n) {
for (m=n; m<=cn; ++m) {
ans[cn][n][m] = ans[cn][m][n] = calc();
}
}
} printAns();
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif init(); #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
(2) AC程序
/* 2170 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
#define INF 0x3f3f3f3f
#define mset(a, val) memset(a, (val), sizeof(a)) int ans[][] = {
{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}
}; int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int n, w, h; while (scanf("%d%d%d",&n,&w,&h)!=EOF) {
--n;
--w;
--h;
cout << ans[n][w*+h] << endl;
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
4. 数据生成器
import sys
import string
from random import randint, shuffle def GenData(fileName):
with open(fileName, "w") as fout:
t = 1
for tt in xrange(t):
for j in xrange(1, 11):
for i in xrange(1, j+1):
for k in xrange(1, j+1):
fout.write("%d %d %d\n" % (j, i, k)) def MovData(srcFileName, desFileName):
with open(srcFileName, "r") as fin:
lines = fin.readlines()
with open(desFileName, "w") as fout:
fout.write("".join(lines)) def CompData():
print "comp"
srcFileName = "F:\Qt_prj\hdoj\data.out"
desFileName = "F:\workspace\cpp_hdoj\data.out"
srcLines = []
desLines = []
with open(srcFileName, "r") as fin:
srcLines = fin.readlines()
with open(desFileName, "r") as fin:
desLines = fin.readlines()
n = min(len(srcLines), len(desLines))-1
for i in xrange(n):
ans2 = int(desLines[i])
ans1 = int(srcLines[i])
if ans1 > ans2:
print "%d: wrong" % i if __name__ == "__main__":
srcFileName = "F:\Qt_prj\hdoj\data.in"
desFileName = "F:\workspace\cpp_hdoj\data.in"
GenData(srcFileName)
MovData(srcFileName, desFileName)