【魔板】 （C++代码）

解题思路:





注意事项:





参考代码:

#include <cstdio>

#include <cstring>

const int maxn = 100000 + 10;

const int hashsize = 100000 + 10;

typedef int State[8];

State st[maxn], goal; 

int fa[maxn], hash[maxn]; 

char tm[maxn];  // 状态转换方式

const char ms[3] = {'A', 'B', 'C'};

const int ma[8] = {7, 6, 5, 4, 3, 2, 1, 0};

const int mb[8] = {3, 0, 1, 2, 5, 6, 7, 4};

const int mc[8] = {0, 6, 1, 3, 4, 2, 5, 7};

int head[hashsize], next[hashsize];

int getHash(State& s)

{

int ans = 0;

for (int i = 0; i < 8; ++i) ans = ans*10 + s[i];

return ans % hashsize;

}

int try_into_insert(int s)

{

int h = getHash(st[s]);

int u = head[h];

while (u)

{

if (!memcmp(st[u], st[s], sizeof(st[s]))) return 0;  // 找到了，插入失败

u = next[u];

}

next[s] = head[h];

head[h] = s;

return 1;

}

void transform(State& s, State& t, char ch)

{

if (ch == 'A') // 交换上下两行

for (int i = 0; i < 8; ++i) t[i] = s[ma[i]];

else if (ch == 'B')

for (int i = 0; i < 8; ++i) t[i] = s[mb[i]];

else if (ch == 'C')

for (int i = 0; i < 8; ++i) t[i] = s[mc[i]];

}

int bfs()

{

int count = 0;

int front = 1, rear = 2;

while (front < rear)

{

State& s = st[front];

if (memcmp(goal, s, sizeof(s)) == 0) return front;  // 找到目标状态，成功返回

for (int i = 0; i < 3; ++i)

{

State& t = st[rear];

transform(s, t, ms[i]);

fa[rear] = front; tm[rear] = ms[i];

if (try_into_insert(rear)) rear++;

}

front++;

}

return 0;

}

int main()

{

char str1[10], str2[10];

while (~scanf("%s%s", str1, str2))

{

char paths[maxn];

memset(hash, 0, sizeof(hash));  // 初始化哈希表

memset(head, 0, sizeof(head));  // 初始化哈希表

memset(next, 0, sizeof(next));  // 初始化哈希表

for (int i = 0; i < 8; ++i) { st[1][i] = str1[i]-'0'; } 

for (int i = 0; i < 8; ++i) { goal[i] = str2[i]-'0'; }

int u = bfs(), p = 0; 

while (u != 1) { paths[p++] = tm[u]; u = fa[u]; }

for (int i = p-1; i >= 0; --i) printf("%c", paths[i]);

printf("\n");

}

return 0;

}