穷举了华容道的所有局面
盘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亿，1G=10亿。在Intel N100上，(total++ & 0xfffffff) == 0时print，不到一秒一个。单线程跑的，Debian依然很流畅。像样的电脑约能每秒处理3亿个。
容易改成12线程，每个线程处理一个曹老板（的位置）。共享的数据是只读的。
a.out 1 2 4为1x2x4型号生成数据124.dat; a.out 1 2 print layers; 依次类推。a.out搜索。
alias了gcc='g++ -msse4.2'，别忘了-O3编译。
水平有限，垂垂老矣，脑袋昏昏——程序（很）可能有bug，且保留不再改bug的权力。:-)
接下来把每个局面看作顶点，用图论的方法找最短路径？我是不折腾了。
找到了37,946,880个局面——好像多了。不能把4层叠起来的结果去unique吧？但每层可以且应该unique下吧（我没做）？
#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(intww, 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 感谢分享，学习下。 感谢分享，学习下。
页:
[1]