#哈希，广搜#洛谷 2730 SSL 1692 魔板

本文主要是介绍#哈希，广搜#洛谷 2730 SSL 1692 魔板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

求从初始状态最少需要多少步到目标状态。

分析

首先这道题显而易见就是广搜，不过怎样标记它的状态？
所以用哈希。
因为理论上最多需要8! =40320，按照经验来说40320*1.2=48384，不过因为它不是质数，所以就用48383

代码

#include <cstdio>
#include <cstring>
#define p 48383
using namespace std;
const char rules[3][8]={{'8','7','6','5','4','3','2','1'},{'4','1','2','3','6','7','8','5'},{'1','7','2','4','5','3','6','8'}};
char a[9],answer[p+1],list[p+1][9],hash[p+1][9],s[p+1]; int ans,f[p+1];
bool check(char *s){int k=0,i=0;for (int i=1;i<=8;i++) k=k*10+s[i]-48;int orig=k%p;while (i<p&&!strstr(hash[(orig+i)%p]+1,s+1)&&hash[(orig+i)%p][1]!='\0') i++;if (strstr(hash[(orig+i)%p]+1,s+1)) return true; else strcpy(hash[(orig+i)%p]+1,s+1); return false;
}
void print(int tail){if (!tail) return;print(f[tail]);if (answer[tail]!='@') s[++ans]=answer[tail];
}
void bfs(){int head=0,tail=1; answer[1]=64;strcpy(list[1]+1,"12345678"); strcpy(hash[12345678%p]+1,list[1]+1);do{head++;for (int i=0;i<3;i++){f[++tail]=head;//标记前一步answer[tail]=i+65;strcpy(list[tail]+1,list[head]+1);for (int j=1;j<=8;j++) list[tail][j]=list[head][rules[i][j-1]-48];if (check(list[tail])) tail--;//以前走过if (strstr(list[tail]+1,list[0]+1)){print(tail);return;} //到达目标}}while (head<tail);
}
int main(){for (int i=1;i<=8;i++) scanf("%d",&a[i]),a[i]+=48; strcpy(list[0]+1,a+1);if (strstr(list[0]+1,"12345678")) {putchar('0'); return 0;}//目标状态为初始状态bfs(); printf("%d\n",ans); puts(s+1);return 0;
}