华容道有37,946,880个局面
盘4x5=20. 有两个空，它们的位置有C(20,2)=190种，这可不是局面的总数，因为没有考虑块的大小，移动时不能把曹老板四马分尸。
分（图）层和分类。2x2x1曹, 2x1x1关, 1x2x4张等, 1x1x4卒。每类占据一层。
先穷举每类在它的图层上有多少种摆法，结果如下：
[*]2x2x1 12
[*]2x1x1 15
[*]1x2x4 21264
[*]1x1x4 116,280
然后搜索4层。把4层的bitmask or起来，如果有遮挡，就会有不止两个空(0)，1的个数就不是18，用_mm_popcnt_u32数1的个数。
12*15*21264*116280/1e8≈4451亿，可裁剪掉很多：int popcnt = { 4, 6, 14, 18 }; 符合条件才搜下一层。
g++ -msse4.2 -O3, Intel N100, 11.363秒。
容易改成12线程，每个线程处理一个曹老板（的位置）。像八皇后一样可不用锁。
用法：
[*]a.out 1 2 4 为1x2x4型生成数据124.dat
[*]a.out 1 2 print layers
[*]a.out 搜索
请看开始处图片左右两边的两个长条。拿掉所有别的块后，它们是对称的，因此应抹掉图案，按一种情况算？它们旁边的块可能不同，因此一块可以动另一个不可以。所以：
[*]按不同情况。
[*]bitmask只用来判断冲突，局面还是存(x,y)，一个字节可存下，10个块10个字节。
接下来可考虑每个局面看作顶点，用图论的方法找最短路径。
#include #include #include #include typedef unsigned uint;FILE* open_file (int w, int h, int n, const char* mode) {charfn;sprintf(fn, "%d%d%d.dat", w, h, n);return fopen(fn, mode);}struct LayerAry {uint* ary;int len;operator uint* () { return ary; }void load (int w, int h, int n) { FILE* fp = open_file(w, h, n, "rb"); fseek(fp, 0, SEEK_END); ary = new uint; fseek(fp, 0, SEEK_SET); fread(ary, 4, len, fp); fclose(fp); printf("%d%d%d %d\n", w, h, n, len);}~LayerAry () { delete[] ary; }};struct GetLayer {uint b, w, h;FILE* fp;GetLayer(int ww, int hh, int n) : w(ww), h(hh) { fp = open_file(w, h, n, "wb"); memset(b, 0, sizeof(b)); search(n); fclose(fp);}void print() { for (int y = 0; y < 5; y++) { for (int x = 0; x < 4; x++) putchar(b ? '*' : '.'); puts(""); }}void save() { uintbits = 0; for (int y = 0; y < 5; y++) { for (int x = 0; x < 4; x++) bits |= b4 || y + h > 5) return false; for (int yy = y; yy < y + h; yy++) for (int xx = x; xx < x + w; xx++) if (b) return false; for (int yy = y; yy < y + h; yy++) for (int xx = x; xx < x + w; xx++) b = 1; return true;}void unput(int x, int y) { for (int yy = y; yy < y + h; yy++) for (int xx = x; xx < x + w; xx++) b = 0;}void search (int n) { for (int y = 0; y < 5; y++) for (int x = 0; x < 4; x++) { if (!put(x, y)) continue; if (n == 1) save(); else search(n - 1); unput(x, y); }}};void print (uint bits) {printf("%05x%3d\n", bits, _mm_popcnt_u32(bits));for (int y = 0; y < 5; y++) { for (int x = 0; x < 4; x++) putchar(bits & (1 谢谢分享，试用一下 yyds。多谢分享 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 感谢分享 感谢分享，下载保存了，貌似很强大
页:
[1]