保持有关访问状态信息的想法
|
我现在正在制作15谜题解算器（用C ++），但我的程序不仅要解决15谜题，还必须解决3x4谜题，8x8谜题等...-> X x Y谜题。我必须以某种方式保留有关访问状态的信息，我的第一个想法是制作树，例如：
难题：
状态1
1 2
3 0
状态2
1 3
0 2
我留在树上：
根-> 1-> 2-> 3-> 0
\\ _
\\-> 3-> 0-> 2
这对于拼图5x3、6x6等也适用于所有拼图
这个想法行得通，但是浪费了很多内存，并且添加节点需要一些时间：/因此效率很低。
下一个想法是将访问状态保留在stl的std :: map <>中，但是我不知道如何制作良好的哈希函数-从拼图状态中创建快捷方式（因为我不必存储拼图状态，我只需要访问信息，对std :: map的键有什么想法，还是要保留有关状态信息的其他想法？
没有找到相关结果
已邀请:
3 个回复
磁辫覆氓
这将被夷为平地然后转换为以4为底的数字：这将唯一地标识任何难题的任何给定状态。吠强祷豪硅
template<unsigned X, unsigned Y> class PuzzleState { unsigned char state[X*Y]; public: void set(unsigned x, unsigned y, unsigned char v) { state[x+X*y] = v; } unsigned get(unsigned x, unsigned y) { return state[x+X*y]; } bool operator<(const PuzzleState<X, Y>& other) const { return memcmp(state, other.state, X*Y) < 0; } };与和方法一起使用即可。在测试性能是否仍然不合适之后，可以使用简单的哈希函数（例如Rolling hash）来抛出哈希表，而不是the7。梦话快家腹