题解 P2730 【魔板 Magic Squares】
getchar123
2018-12-23 07:45:07
第一次写题解,不太会用emm将就一下吧。
步入正题:广搜+map去重
可以先把它当字符串处理,再找出ABC三种操作的规律,用函数模拟。map里存操作序列。
贴代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
string a;
map<string,string>m;
queue<string>q;
void A(string x){
string xx=x;
for(int i=0;i<4;i++){
char x1=x[i];
x[i]=x[7-i];
x[7-i]=x1;
}
if(m.count(x)==0){//没有出现过
q.push(x);
m[x]=m[xx]+'A';
}
return;
}
void B(string x){
string xx=x;
x[0]=xx[3],x[1]=xx[0],x[2]=xx[1],x[3]=xx[2],x[4]=xx[5],x[5]=xx[6],x[6]=xx[7],x[7]=xx[4];
if(m.count(x)==0){
q.push(x);
m[x]=m[xx]+'B';
}
return;
}
void C(string x){
string xx=x;
x[1]=xx[6],x[2]=xx[1],x[5]=xx[2],x[6]=xx[5];
if(m.count(x)==0){
q.push(x);
m[x]=m[xx]+'C';
}
return;
}
void bfs(){
q.push("12345678");
m["12345678"]="";
while(q.empty()==false){
A(q.front());
B(q.front());
C(q.front());
if(m.count(a)!=0){//当出现目标序列
cout<<m[a].size()<<endl<<m[a];
return;
}
q.pop();
}
return;
}
int main(){
for(int i=0;i<8;i++){
char a1;
cin>>a1;
a+=a1;
getchar();
}
bfs();
return 0;
}
```