华容道 BFS DFS C++ Python 短程序

图片来自百度华容道吧。第二/三步卒子像军旗的工兵在铁道上跑——比我们的局面变化数少。
C++版注释掉判断找到解：//if (a[0][1] == 3) { print_path(); break; }
程序不崩，queue_tail = 14,950,080，我的解释是：从此局面出发总共有这么多。和这个不矛盾。
“诗云”版华容道应该是可行的。
gcc 12的STL的set不快，这个程序比那个上面那个慢多了。set底层是树，unordered_set底层是Hash表。可Hash表都用自己的。

1. E = '　' # 全角空格
3. class Brd:
4.   def __str__(m): return '\n'.join([''.join(r) for r in m.b])
5.   def totuple(m): return tuple(tuple(r) for r in m.b)
7.   def put(m, blks):
8.     m.b = [[E] * 4 for _ in range(5)]
9.     for b in blks:
10.       if b.x < 0 or b.x + b.w > 4 or b.y < 0 or b.y + b.h > 5: return False
11.       for y in range(b.y, b.y + b.h):
12.         for x in range(b.x, b.x + b.w):
13.           if m.b[y][x] != E: return False
14.           m.b[y][x] = b.name
15.     return True
17. class Blk:
18.   def __init__(m, name, x, y, w = 1, h = 1):
19.     m.name = name; m.x = x; m.y = y; m.w = w; m.h = h; m.old = []
21.   def step(m, dx, dy):
22.     m.old.append((m.x, m.y)); m.x += dx; m.y += dy
24.   def back(m): (m.x, m.y) = m.old.pop()
26. brd = Brd() # 全局临时brd．
27. # 每个blk有自己的old[]，等于我们自己管理一些堆栈。
28. blks = [
29.   Blk('曹', 1, 0, 2, 2),
30.   Blk('关', 1, 2, 2, 1),
31.   Blk('张', 0, 3, 1, 2),
32.   Blk('黄', 1, 3, 1, 2),
33.   Blk('赵', 2, 3, 1, 2),
34.   Blk('马', 3, 3, 1, 2),
35.   Blk('甲', 0, 0),
36.   Blk('乙', 0, 1),
37.   Blk('丙', 3, 0),
38.   Blk('丁', 3, 1)
39. ]
40. cc = blks[0]
41. brd.put(blks); seen = set(); path = []
43. def search (n):
44.   if cc.y == 3: return True
46.   s = str(brd) # 都可以，速度本例看不出差别
47.   # s = brd.totuple()
48.   if s in seen: return False
49.   seen.add(s)
51.   for b in blks:
52.     for (dx, dy) in [[-1,0],[1,0],[0,-1],[0,1]]:
53.       b.step(dx, dy)
54.       if brd.put(blks):
55.         path.append(str(brd))
56.         if search(n + 1): return True
57.         path.pop()
58.       b.back()
60.   return False
62. import sys
63. sys.setrecursionlimit(10000)
65. if search(0): print(len(path), path[-1], path[0], sep='\n\n')

复制代码

[code]#include #include #include #include #include #include using namespace std;const char* NM[] = { "曹", "关", "张", "黄", "赵", "马", "丁", "丙", "乙", "甲" };const int W[] = { 2, 2, 1, 1, 1, 1, 1, 1, 1, 1 };const int H[] = { 2, 1, 2, 2, 2, 2, 1, 1, 1, 1 };const int D[4][2] = { 0, -1, 0, 1, -1, 0, 1, 0 };struct State {  uint64_t  xys; // xy坐标们  int p; // 局面路径的previous  // int next; // Hash表里的next  bool operator< (const State& that) const { return xys < that.xys; }  State& operator= (int a[10][2]);  void toary(int a[10][2]);  void operator= (const char* s);  void print();};State& State:perator= (int a[10][2]) {  xys = 0;  for (int i = 0; i < 10; i++) {    uint64_t  x = a[0], y = a[1];    xys |= ((x  (i * 5);    a[0] = (xy >> 3) & 3; // x    a[1] = xy & 7; // y  }}void State:perator= (const char* s) {  int a[10][2] = {}, p = 6;  for (int x = 3; x >= 0; x--)    for (int y = 4; y >= 0; y--) {    #define CASE(c, i) case c: a[0] = x; a[1] = y; break;    switch (s[x * 5 + y]) {    CASE('c', 0) CASE('g', 1) // 曹关    CASE('z', 2) CASE('h', 3) // 张黄    CASE('l', 4) CASE('m', 5) // 子龙(l) 马    case 'p': a[p][0] = x; a[p++][1] = y;    }  }  *this = a;}void State::print () {  const char* b[5][4] = {};  int a[10][2]; toary(a);  for (int i = 0; i < 10; i++) {    int x = a[0], y = a[1];    for (int yy = y; yy < y + H; yy++)      for (int xx = x; xx < x + W; xx++)        b[yy][xx] = NM;  }  for (int y = 0; y < 5; y++) {    for (int x = 0; x < 4; x++) printf("%s", b[y][x] ? : "　");    puts("");  }  puts("");}enum { QMAX = 100 * 1000 * 1000 };State states[QMAX + 40];int qh, qt = 1; // queue head, tailset  seen; // 改Hash表，和states二合一bool can_move (int a[10][2], int i, int j) {  // 无论成功失败, a都被修改，需要被恢复  // 别优化，a[0]和a[1]要一起改  const int x = (a[0] += D[j][0]);  const int y = (a[1] += D[j][1]);  if (x < 0 || x + W > 4) return false;  if (y < 0 || y + H > 5) return false;  uint32_t  bits = 0;  for (int i = 0; i < 10; i++) {    const int x = a[0], y = a[1];    for (int yy = y; yy < y + H; yy++)      for (int xx = x; xx < x + W; xx++)        bits |= 1