beifeng


私信TA

用户名:beifeng

访问量:2785

签 名:

等  级
排  名 15596
经  验 537
参赛次数 0
文章发表 3
年  龄 0
在职情况 学生
学  校 中国计量大学
专  业

  自我简介:

TA的其他文章

解题思路:





注意事项:





参考代码:

#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;

}


 

0.0分

1 人评分

  评论区