华容道有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] = { 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[1][2]
  
• a.out 搜索
  

请看开始处图片左右两边的两个长条。拿掉所有别的块后，它们是对称的，因此应抹掉图案，按一种情况算？它们旁边的块可能不同，因此一块可以动另一个不可以。所以：

• 按不同情况。
  
• bitmask只用来判断冲突，局面还是存(x,y)，一个字节可存下，10个块10个字节。
  

接下来可考虑每个局面看作顶点，用图论的方法找最短路径。
[code]#include #include #include #include typedef unsigned uint;FILE* open_file (int w, int h, int n, const char* mode) {  char  fn[256];  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[len = ftell(fp) / 4];    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[5][4], 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[y][x] ? '*' : '.');     puts("");    }  }  void save() {    uint  bits = 0;    for (int y = 0; y < 5; y++) {     for (int x = 0; x < 4; x++)      bits |= b[y][x]  4 || y + h > 5) return false;    for (int yy = y; yy < y + h; yy++) for (int xx = x; xx < x + w; xx++)      if (b[yy][xx]) return false;    for (int yy = y; yy < y + h; yy++) for (int xx = x; xx < x + w; xx++) b[yy][xx] = 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[yy][xx] = 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