题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1430
题意:给你两串字符串,有三种操作,让你从第一个变到第二个最小需要的变换步数。
题解:这道题如果每个直接用BFS搜素的话会超时,要么用双向BFS,要么用BFS预处理好,然后直接输出路径即可,但是这里有个技巧,就是开始的字符串不一定是前面搜素的,所以我们可以将两个字符串变换成他们的相对位置,相当于第一个字符串是预处理的第一个状态。
BFS预处理AC代码:
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <cmath> #include <vector> #include <list> #include <deque> #include <queue> #include <iterator> #include <stack> #include <map> #include <set> #include <algorithm> #include <cctype> #include <ctime> #pragma comment(linker, "/STACK:16777216") using namespace std; typedef __int64 LL; const int N=44444; const int M=1; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); const double eps=1e-7; char q[N][10],tmp[10],op[N]; int last[N],ta,he; map<string,int> pos; void op1(char *s) { reverse(s,s+8);//反转 } void op2(char *s) { rotate(s,s+3,s+4); rotate(s+4,s+5,s+8); } void op3(char *s) { char c=s[1]; s[1]=s[6]; s[6]=s[5]; s[5]=s[2]; s[2]=c; } void BFS() { for(int i=0;i<8;i++) tmp[i]=i+'0'; tmp[8]=0; pos.clear(); ta=he=0; strcpy(q[ta],tmp); pos[tmp]=ta; last[ta]=-1; op[ta++]=0; while(he<ta) { strcpy(tmp,q[he]); op1(tmp); if(pos.find(tmp)==pos.end()) { strcpy(q[ta],tmp); pos[tmp]=ta; last[ta]=he; op[ta++]='A'; } strcpy(tmp,q[he]); op2(tmp); if(pos.find(tmp)==pos.end()) { strcpy(q[ta],tmp); pos[tmp]=ta; last[ta]=he; op[ta++]='B'; } strcpy(tmp,q[he]); op3(tmp); if(pos.find(tmp)==pos.end()) { strcpy(q[ta],tmp); pos[tmp]=ta; last[ta]=he; op[ta++]='C'; } he++; } } char be[10],en[10],con[10]; char ans[N]; int main() { BFS(); while(~scanf("%s%s",be,en)) { for(int i=0;i<8;i++) { int t=0; while(be[i]!=en[t]) t++; con[t]=i+'0'; } con[8]=0;//con是相对状态 int cur=pos[con],k=0; while(cur) { ans[k++]=op[cur]; cur=last[cur]; } for(int i=k-1;i>=0;i--) putchar(ans[i]); puts(""); } return 0; }