华容道 BFS DFS C++ Python 短程序
图片来自百度华容道吧。第二/三步卒子像军旗的工兵在铁道上跑——比我们的局面变化数少。C++版注释掉判断找到解：//if (a == 3) { print_path(); break; }
程序不崩，queue_tail = 14,950,080，我的解释是：从此局面出发总共有这么多。和这个不矛盾。
“诗云”版华容道应该是可行的。
gcc 12的STL的set不快，这个程序比那个上面那个慢多了。set底层是树，unordered_set底层是Hash表。可Hash表都用自己的。
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 = [ * 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 False
for y in range(b.y, b.y + b.h):
for x in range(b.x, b.x + b.w):
if m.b != E: return False
m.b = b.name
return True
class 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 += dy
def 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
brd.put(blks); seen = set(); path = []
def search (n):
if cc.y == 3: return True
s = str(brd) # 都可以，速度本例看不出差别
# s = brd.totuple()
if s in seen: return False
seen.add(s)
for b in blks:
for (dx, dy) in [[-1,0],,,]:
b.step(dx, dy)
if brd.put(blks):
path.append(str(brd))
if search(n + 1): return True
path.pop()
b.back()
return False
import sys
sys.setrecursionlimit(10000)
if search(0): print(len(path), path[-1], path, sep='\n\n')#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 = { 0, -1, 0, 1, -1, 0, 1, 0 };struct State {uint64_txys; // xy坐标们int p; // 局面路径的previous// int next; // Hash表里的nextbool operator< (const State& that) const { return xys < that.xys; }State& operator= (int a);void toary(int a);void operator= (const char* s);void print();};State& State::operator= (int a) {xys = 0;for (int i = 0; i < 10; i++) { uint64_tx = a, y = a; xys |= ((x(i * 5); a = (xy >> 3) & 3; // x a = xy & 7; // y}}void State::operator= (const char* s) {int a = {}, p = 6;for (int x = 3; x >= 0; x--) for (int y = 4; y >= 0; y--) { #define CASE(c, i) case c: a = x; a = y; break; switch (s) { CASE('c', 0) CASE('g', 1) // 曹关 CASE('z', 2) CASE('h', 3) // 张黄 CASE('l', 4) CASE('m', 5) // 子龙(l) 马 case 'p': a = x; a = y; }}*this = a;}void State::print () {const char* b = {};int a; toary(a);for (int i = 0; i < 10; i++) { int x = a, y = a; for (int yy = y; yy < y + H; yy++) for (int xx = x; xx < x + W; xx++) b = NM;}for (int y = 0; y < 5; y++) { for (int x = 0; x < 4; x++) printf("%s", b ? : " "); puts("");}puts("");}enum { QMAX = 100 * 1000 * 1000 };State states;int qh, qt = 1; // queue head, tailsetseen; // 改Hash表，和states二合一bool can_move (int a, int i, int j) {// 无论成功失败, a都被修改，需要被恢复// 别优化，a和a要一起改const int x = (a += D);const int y = (a += D);if (x < 0 || x + W > 4) return false;if (y < 0 || y + H > 5) return false;uint32_tbits = 0;for (int i = 0; i < 10; i++) { const int x = a, y = a; for (int yy = y; yy < y + H; yy++) for (int xx = x; xx < x + W; xx++) bits |= 1 热心回复！
页:
[1]