图片来自百度华容道吧。第二步卒子像军旗的工兵在铁道上跑——比我们的局面变化数少。
E = ' ' # 全角空格class Brd:def __str__(m): return '\n'.join([''.join(r) for r in m.b])def totuple(m): return tuple(tuple(r) for r in m.b)def put(m, blks):m.b = [[E] * 4 for _ in range(5)]for b in blks:if b.x < 0 or b.x + b.w > 4 or b.y < 0 or b.y + b.h > 5: return Falsefor y in range(b.y, b.y + b.h):for x in range(b.x, b.x + b.w):if m.b[y][x] != E: return Falsem.b[y][x] = b.namereturn Trueclass Blk:def __init__(m, name, x, y, w = 1, h = 1):m.name = name; m.x = x; m.y = y; m.w = w; m.h = h; m.old = []def step(m, dx, dy):m.old.append((m.x, m.y)); m.x += dx; m.y += dydef back(m): (m.x, m.y) = m.old.pop()brd = Brd() # 全局临时brd． # 每个blk有自己的old[]，等于我们自己管理一些堆栈。 blks = [Blk('曹', 1, 0, 2, 2),Blk('关', 1, 2, 2, 1),Blk('张', 0, 3, 1, 2),Blk('黄', 1, 3, 1, 2),Blk('赵', 2, 3, 1, 2),Blk('马', 3, 3, 1, 2),Blk('甲', 0, 0),Blk('乙', 0, 1),Blk('丙', 3, 0),Blk('丁', 3, 1) ] cc = blks[0] brd.put(blks); seen = set(); path = []def search (n):if cc.y == 3: return Trues = str(brd) # 都可以，速度本例看不出差别# s = brd.totuple()if s in seen: return Falseseen.add(s)for b in blks:for (dx, dy) in [[-1,0],[1,0],[0,-1],[0,1]]:b.step(dx, dy)if brd.put(blks):path.append(str(brd))if search(n + 1): return Truepath.pop()b.back()return Falseimport sys sys.setrecursionlimit(10000)if search(0): print(len(path), path[-1], path[0], sep='\n\n')
#include <stdio.h> #include <stdint.h> #include <stdlib.h> #include <string.h> #include <nmmintrin.h> #include <set> 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表里的nextbool 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::operator= (int a[10][2]) {xys = 0;for (int i = 0; i < 10; i++) {uint64_t x = a[i][0], y = a[i][1];xys |= ((x << 3) | y) << (i * 5);}return *this; }void State::toary (int a[10][2]) {for (int i = 0; i < 10; i++) {uint xy = xys >> (i * 5);a[i][0] = (xy >> 3) & 3; // xa[i][1] = xy & 7; // y } }void State::operator= (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[i][0] = x; a[i][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[i][0], y = a[i][1];for (int yy = y; yy < y + H[i]; yy++)for (int xx = x; xx < x + W[i]; xx++)b[yy][xx] = NM[i];}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, tail set<State> seen; // 改Hash表，和states二合一bool can_move (int a[10][2], int i, int j) {// 无论成功失败, a[i]都被修改，需要被恢复// 别优化，a[i][0]和a[i][1]要一起改const int x = (a[i][0] += D[j][0]);const int y = (a[i][1] += D[j][1]);if (x < 0 || x + W[i] > 4) return false;if (y < 0 || y + H[i] > 5) return false;uint32_t bits = 0;for (int i = 0; i < 10; i++) {const int x = a[i][0], y = a[i][1];for (int yy = y; yy < y + H[i]; yy++)for (int xx = x; xx < x + W[i]; xx++)bits |= 1 << (yy * 4 + xx);}return _mm_popcnt_u32(bits) == 18; }// 逆序输出。图片里的一步可能等于我们的多步。 void print_path () {int p = qh;while (p != -1) {states[p].print();p = states[p].p;} }int main () {states[0] = "pp zz""ccghh""ccgll""pp mm";states[0].p = -1;seen.insert(states[0]);for (; (qt < QMAX) && (qh < qt); qh++) {int a[10][2]; states[qh].toary(a);if (a[0][1] == 3) { print_path(); break; }for (int i = 0; i < 10; i++)for (int j = 0; j < 4; j++) {if (can_move(a, i, j)) {states[qt] = a;if (seen.find(states[qt]) == seen.end()) {seen.insert(states[qt]);states[qt++].p = qh;}// a[0][1]和(xys & 7)都是曹操的y坐标，按它排序？ }a[i][0] -= D[j][0]; a[i][1] -= D[j][1];}}return 0; }
bbb