[bfs]hdoj 5012
5454 ワード
おおよその意味
2つの色子を与えて、1つ目の色子が何回反転した後に2つ目の色子になることができるかを聞きます
大まかな考え方:
暴力は乗り越えられる
2つの色子を与えて、1つ目の色子が何回反転した後に2つ目の色子になることができるかを聞きます
大まかな考え方:
暴力は乗り越えられる
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
class nod{
public :
int face[6];
int res;
}aa1,aa2;
int vis[7][7][7][7][7][7],ans,num[6];
void turn1(nod& node){
int i;
int mark[6];
for(i=0;i<6;i++){
mark[i]=node.face[i];
}
node.face[0]=mark[3];
node.face[1]=mark[2];
node.face[2]=mark[0];
node.face[3]=mark[1];
node.face[4]=mark[4];
node.face[5]=mark[5];
}
void turn2(nod& node){
int i;
int mark[6];
for(i=0;i<6;i++){
mark[i]=node.face[i];
}
node.face[0]=mark[2];
node.face[1]=mark[3];
node.face[2]=mark[1];
node.face[3]=mark[0];
node.face[4]=mark[4];
node.face[5]=mark[5];
}
void turn3(nod& node){
int i;
int mark[6];
for(i=0;i<6;i++){
mark[i]=node.face[i];
}
node.face[0]=mark[5];
node.face[1]=mark[4];
node.face[2]=mark[2];
node.face[3]=mark[3];
node.face[4]=mark[0];
node.face[5]=mark[1];
}
void turn4(nod& node){
int i;
int mark[6];
for(i=0;i<6;i++){
mark[i]=node.face[i];
}
node.face[0]=mark[4];
node.face[1]=mark[5];
node.face[2]=mark[2];
node.face[3]=mark[3];
node.face[4]=mark[1];
node.face[5]=mark[0];
}
bool bfs(){
int i;
queue<nod>que;
que.push(aa1);
while(!que.empty()){
nod node;
node=que.front();
que.pop();
if(node.face[0]==aa2.face[0]&&node.face[1]==aa2.face[1]&&node.face[2]==aa2.face[2]&&node.face[3]==aa2.face[3]&&node.face[4]==aa2.face[4]&&node.face[5]==aa2.face[5])
{
ans=node.res;
return 1;
}
node.res++;
for(i=0;i<6;i++){
num[i]=node.face[i];
}
turn1(node);
// cout<<"node1"<<node.face[0]<<" "<<node.face[1]<<" "<<node.face[2]<<" "<<node.face[3]<<" "<<node.face[4]<<" "<<node.face[5]<<endl;
if(!vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]){
vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]=1;
que.push(node);
}
for(i=0;i<6;i++){
node.face[i]=num[i];
}
turn2(node);
// cout<<"node2"<<node.face[0]<<" "<<node.face[1]<<" "<<node.face[2]<<" "<<node.face[3]<<" "<<node.face[4]<<" "<<node.face[5]<<endl;
if(!vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]){
vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]=1;
que.push(node);
}
for(i=0;i<6;i++){
node.face[i]=num[i];
}
turn3(node);
// cout<<"node3"<<node.face[0]<<" "<<node.face[1]<<" "<<node.face[2]<<" "<<node.face[3]<<" "<<node.face[4]<<" "<<node.face[5]<<endl;
if(!vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]){
vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]=1;
que.push(node);
}
for(i=0;i<6;i++){
node.face[i]=num[i];
}
turn4(node);
// cout<<"node4"<<node.face[0]<<" "<<node.face[1]<<" "<<node.face[2]<<" "<<node.face[3]<<" "<<node.face[4]<<" "<<node.face[5]<<endl;
if(!vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]){
vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]=1;
que.push(node);
}
}
return 0;
}
int main(){
int i;
while(cin>>aa1.face[0]){
ans=0;
for(i=1;i<6;i++)cin>>aa1.face[i];
for(i=0;i<6;i++)cin>>aa2.face[i];
memset(vis,0,sizeof(vis));
aa1.res=0;
vis[aa1.face[0]][aa1.face[1]][aa1.face[2]][aa1.face[3]][aa1.face[4]][aa1.face[5]]=1;
if(bfs())cout<<ans<<endl;
else cout<<-1<<endl;
}
return 0;
}