ZOJ 2477 Magic Cube暴力、アナログ難易度:0
2827 ワード
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1477
IDA*を使ったほうがいいかもしれませんが、時間の余裕があるのでデータが簡単で、しかも記録状態が面倒なので、直接暴力を振るいます。
IDA*を使ったほうがいいかもしれませんが、時間の余裕があるのでデータが簡単で、しかも記録状態が面倒なので、直接暴力を振るいます。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
char maz[54];
char readchar(){
char ch=0;
while(!isalpha(ch)){
ch=getchar();
}
return ch;
}
const int cell[6][9]={// ,
{4,0,1,2,3,5,6,7,8},{22,9,10,11,21,23,33,34,35},{25,12,13,14,24,26,36,37,38},
{28,15,16,17,27,29,39,40,41},{31,18,19,20,30,32,42,43,44},{49,45,46,47,48,50,51,52,53}
};
const int change[12][20]={//change[cnt][i]: cnt i ,change[cnt^1][i]: cnt i
{11,23,35,34,33,21, 9,10,51,48,45,36,24,12, 6, 3, 0,20,32,44},
{ 9,10,11,23,35,34,33,21,36,24,12, 6, 3, 0,20,32,44,51,48,45},
{14,13,26,38,37,36,24,12,45,46,47,39,27,15, 8, 7, 6,11,23,35},
{12,24,13,14,26,38,37,36,39,27,15, 8, 7, 6,11,23,35,45,46,47},
{17,29,41,40,39,27,15,16,47,50,53,42,30,18, 2, 5, 8,14,26,38},
{15,16,17,29,41,40,39,27,42,30,18, 2, 5, 8,14,26,38,47,50,53},
{18,19,20,32,44,43,42,30,53,52,51,33,21, 9, 0, 1, 2,17,29,41},
{42,30,18,19,20,32,44,43,33,21, 9, 0, 1, 2,17,29,41,53,52,51},
{ 0, 1, 2, 5, 8, 7, 6, 3,12,13,14,15,16,17,18,19,20, 9,10,11},
{ 6, 3, 0, 1, 2, 5, 8, 7,15,16,17,18,19,20, 9,10,11,12,13,14},
{45,46,47,50,53,52,51,48,44,43,42,41,40,39,38,37,36,35,34,33},
{51,48,45,46,47,50,53,52,41,40,39,38,37,36,35,34,33,44,43,42}
};
bool ok(){
for(int i=0;i<6;i++){
for(int j=1;j<9;j++){
if(maz[cell[i][j]]!=maz[cell[i][0]])return false;
}
}
return true;
}
void rot(int ind){
char tmp[54];
copy(maz,maz+54,tmp);
for(int i=0;i<20;i++){
tmp[change[ind][i]]=maz[change[ind^1][i]];
}
copy(tmp,tmp+54,maz);
}
int ans[6];
bool dfs(int cnt){
if(cnt<=0)return ok();
char tmp[54];
copy(maz,maz+54,tmp);
for(int i=0;i<12;i++){
rot(i);
ans[cnt]=i;
if(dfs(cnt-1))return true;
copy(tmp,tmp+54,maz);
}
return false;
}
int main(){
int T;
scanf("%d",&T);
for(int ti=1;ti<=T;ti++){
for(int i=0;i<54;i++)maz[i]=readchar();
for(int i=0;i<=6;i++){
if(i==6){
puts("-1");
break;
}
else if(dfs(i)){
printf("%d
",i);
for(int j=i;j>0;j--){
printf("%d %d
",ans[j]/2,ans[j]&1?-1:1);
}
break;
}
}
}
return 0;
}