HDu 1430マジックプレート(BFS+コント展開)
7393 ワード
この問題を先に見てください.http://blog.csdn.net/u010372095/article/details/9904497
Problem Description
ルービック氏は、ルービックが世界を風靡してから間もなく、その簡略化版である魔板を発明した.マジックボードは8つの同じ大きさのブロックからなり、各ブロックの色は異なり、数字1-8でそれぞれ表すことができます.いずれのタイミングでもマジックボードの状態は、キューブの色のシーケンスで表すことができます.マジックボードの左上隅から、各ブロックの色番号を時計回りに順番に書き、得られた数字のシーケンスは、このときのマジックボードの状態を表すことができます.例えば、シーケンス(1,2,3,4,5,6,7,8)は、魔板の状態が:1 2 3 4 8 7 6で魔板に対して3種類の異なる操作を加えることができることを示し、具体的な操作方法は以下の通りである:A:上下2行交換、上記のように状態87654321 B:各行同時に右シフト、上記のように41236785 Cに変換することができる:中間4つのブロックが1つに順次回転し、上記の図は172453368に変換して魔板の初期状態と目標状態に変換することができます.初期状態から目状態への変換数が最も少ない変換ステップを与えてください.複数の変換スキームがあれば、辞書順が最も小さいものを取ります.
Input
各試験データのセットは、魔板の初期状態と目状態を表す2行を含む.
Output
テストデータのセットごとに、問題を満たす変換手順を出力します.
Sample Input
12345678 17245368 12345678 82754631
Sample Output
C AC
for( i=0;i<8;i++) pos[ch1[i]-'0']=i+1+'0'; for( i=0;i<8;i++) des[i]=pos[str[i]-'0‘];
s=cantor(des);
最初のターゲットを1,2,3,4,5,6,7,8と見なす ;
列は次のとおりです:位置:12345678 12345678
最初:63728145 へん 12345678
終点: 86372541 成 51234876
初:6は1位で、ゴールでは6を探して1で、3は2位で、ゴールでは3を探して2で、順番に類推します.
最初は12345678という順番で木のようなものを作りましたが、そのまま初態から変わらなければ、結果的にいろいろな歩き方があるかもしれません.AもBも目標に行けるかもしれません.複数の道がある場合、Bの道を先に進み、小さい、つまりAから始まる道を出力しなければなりません.どうすればいいのでしょうか.変換の思想を使うことができて、初期状態を12345678に変えて、このようにすれば、私達は最初からこのような順序から計算しました!!まず変換を行い、ターゲットからパスを探してメモし、最終的な親ノード12345678を見つけなければなりません.
/* 63728145 86372541 ACBBBCBBCBCBCABB
次は、12345678 87654321 41236785 17245368 58763214 82754631 34127856 48136275 86354271の順にキューから300を取り出します. 41723685 16745238 65872143 51863724 13645728 58276314 83254761 23418567 3542718 6 57263184 34812756 47836125 58632714 24176853 48123765 41672385 76581432 645728 13 42736815 65187243 52163874 41367285 75823146 51876234 58327614 26318457 68172 453 23541867 38527416 65721843 13487562 35412876 34781256 35867142 51832674 7241 8536 25476183 56732184 24817653 46823175 74163852 48172635 73681542 31827546 764 58132 61472583 34278156 86512437 64587123 65218743 64132857 48167325 27581463 74 523816 43267815 75182346 53176824 25836147 51827364 75481362 12634578 25618347 7 6814532 42358671 26341587 23854167 26578431 64521783 81345627 16387452 67821453 13548762 37512486 83472561 35481726 63581427 34567812 47623815 35186742 57132864 73218456 38167452 72541836 28576413 35671842 12486537 25417863 24681753 6741852 3 75463182 53627184 74816352 43872165 24518637 87365421 74381652 23185467 576413 28 73658412 76145832 73421568 35478216 18654372 83612547 32178546 86451237 62487 513 16527438 64518273 36418572 65432187 52376184 64813257 42867135 26781543 6183 2547 27458163 71423586 64328157 87513462 74582136 75318246 32581476 24536817 463 72815 25183647 56127834 87543621 31265784 17234658 12563478 17685324 73614852 54 236718 47258361 78514362 42635871 28641357 52381674 26354817 72654318 23678541 3 8712546 26457831 68421573 82145367 25478361 81634527 15687342 26784531 41357628 16348572 13754862 78345612 86372451 62718453 83547261 62381547 21876543 63458127 31467582 24768153 83517426 34586172 35718642 65481237 17324568 63814527 7324158 6 72854136 73568421 34571682 81245376 13286457 36871452 12548637 26517483 824675 31 25481673 28136457 67541823 78563412 25361847 17483526 75416832 12456378 68734 215 82765341 87436521 82314675 26385147 45763281 52741638 21485637 57364128 7135 8642 47618325 73645182 27345681 76321458 61287453 73542168 31578426 17854632 745 21638 18365472 84312657 73215468 58642371 83651427 86245137 21654387 13627548 37 281546 16452738 37618452 78123456 36541872 68532417 75231846 16482573 65413827 6 4281357 34518762 82675431 36185472 26758413 27145863 26431578 65428317 18754623 86713542 63128547 87451362 73482516 17532468 74518326 71863542 32458176 21436587 74638152 82516473 24583167 48756213 82743561 63127845 38165274 85643271 3172658 4 15734268 61254783 17263548 81763245 12785634 25841637 17368524 75314682 514362 78 16385274 54723618 46758231 17853624 34268715 47235681 42863571 85236741 57281 364 71845362 52638174 71254638 14587632 72365418 24378651 13875462 52648317 2365 7481 26845731 76354128 48213675 72543618 82134657 81563427 82675314 23684751 541 36287 42157368 27584361 41635728 17648352 51378624 16354782 15427368 */
Problem Description
ルービック氏は、ルービックが世界を風靡してから間もなく、その簡略化版である魔板を発明した.マジックボードは8つの同じ大きさのブロックからなり、各ブロックの色は異なり、数字1-8でそれぞれ表すことができます.いずれのタイミングでもマジックボードの状態は、キューブの色のシーケンスで表すことができます.マジックボードの左上隅から、各ブロックの色番号を時計回りに順番に書き、得られた数字のシーケンスは、このときのマジックボードの状態を表すことができます.例えば、シーケンス(1,2,3,4,5,6,7,8)は、魔板の状態が:1 2 3 4 8 7 6で魔板に対して3種類の異なる操作を加えることができることを示し、具体的な操作方法は以下の通りである:A:上下2行交換、上記のように状態87654321 B:各行同時に右シフト、上記のように41236785 Cに変換することができる:中間4つのブロックが1つに順次回転し、上記の図は172453368に変換して魔板の初期状態と目標状態に変換することができます.初期状態から目状態への変換数が最も少ない変換ステップを与えてください.複数の変換スキームがあれば、辞書順が最も小さいものを取ります.
Input
各試験データのセットは、魔板の初期状態と目状態を表す2行を含む.
Output
テストデータのセットごとに、問題を満たす変換手順を出力します.
Sample Input
12345678 17245368 12345678 82754631
Sample Output
C AC
for( i=0;i<8;i++) pos[ch1[i]-'0']=i+1+'0'; for( i=0;i<8;i++) des[i]=pos[str[i]-'0‘];
s=cantor(des);
最初のターゲットを1,2,3,4,5,6,7,8と見なす ;
列は次のとおりです:位置:12345678 12345678
最初:63728145 へん 12345678
終点: 86372541 成 51234876
初:6は1位で、ゴールでは6を探して1で、3は2位で、ゴールでは3を探して2で、順番に類推します.
最初は12345678という順番で木のようなものを作りましたが、そのまま初態から変わらなければ、結果的にいろいろな歩き方があるかもしれません.AもBも目標に行けるかもしれません.複数の道がある場合、Bの道を先に進み、小さい、つまりAから始まる道を出力しなければなりません.どうすればいいのでしょうか.変換の思想を使うことができて、初期状態を12345678に変えて、このようにすれば、私達は最初からこのような順序から計算しました!!まず変換を行い、ターゲットからパスを探してメモし、最終的な親ノード12345678を見つけなければなりません.
#include<stdio.h>
#include<iostream>
#include<queue>
#include<stack>
#include<string.h>
using namespace std;
typedef struct nn
{
char ch[9];
int son;
}node1;
typedef struct n
{
char way;//
int father;//
}node2;
node2 Node[40321];//
int fac[8]={1,1,2,6,24,120,720,5040};//
int cantor(char s[])// s ,
{
int i,j,k,ans=0;
for(i=0;i<8;i++)
{
k=0;
for(j=i+1;j<8;j++)
if(s[i]>s[j])
k++;
ans+=k*fac[7-i];
}
return ans;
}
void BFS(char ch1[])
{
queue<node1>Q;
node1 now,next;
int i,son,e=0;
char tc;
son=cantor(ch1);
strcpy(now.ch,ch1);now.ch[8]='\0';
now.son=son;Node[son].father=0;//
Q.push(now);
while(!Q.empty())
{
now=Q.front(); Q.pop();
//printf("%s ",now.ch);if(e==300)getchar();e++;
next=now;
for(i=0;i<4;i++) {tc=next.ch[i];next.ch[i]=next.ch[7-i];next.ch[7-i]=tc; }
son=cantor(next.ch); next.son=son;
if(Node[son].father==-1)
{
Node[next.son].father=now.son; Node[next.son].way='A';
Q.push(next);
}
next=now;
tc=next.ch[3];for(i=3;i>0;i--) next.ch[i]=next.ch[i-1]; next.ch[0]=tc;
tc=next.ch[4];for(i=4;i<7;i++) next.ch[i]=next.ch[i+1]; next.ch[7]=tc;
son=cantor(next.ch); next.son=son;
if(Node[son].father==-1)
{
Node[next.son].father=now.son; Node[next.son].way='B';
Q.push(next);
}
next=now;
tc=next.ch[5];next.ch[5]=next.ch[2];next.ch[2]=next.ch[1];next.ch[1]=next.ch[6];next.ch[6]=tc;
son=cantor(next.ch); next.son=son;
if(Node[son].father==-1)
{
Node[next.son].father=now.son; Node[next.son].way='C';
Q.push(next);
}
}
}
int main()
{
int c,s,i;
char str[9];
char ch1[9]={'1','2','3','4','5','6','7','8'};
for(i=0;i<40321;i++)
Node[i].father=-1;
BFS(ch1);
char Way[10000];
while(cin>>ch1>>str)
{
char pos[10];
char des[8];
for( i=0;i<8;i++)//
pos[ch1[i]-'0']=i+1+'0';
for( i=0;i<8;i++)
des[i]=pos[str[i]-'0'];
s=cantor(des);
i=0;
while(0!=s)//
{
Way[i++]=Node[s].way;//printf("7 ");
s=Node[s].father;
}
while(i--)//
{
printf("%c",Way[i]);
}
printf("
");
}
}/* 63728145 86372541 ACBBBCBBCBCBCABB
次は、12345678 87654321 41236785 17245368 58763214 82754631 34127856 48136275 86354271の順にキューから300を取り出します. 41723685 16745238 65872143 51863724 13645728 58276314 83254761 23418567 3542718 6 57263184 34812756 47836125 58632714 24176853 48123765 41672385 76581432 645728 13 42736815 65187243 52163874 41367285 75823146 51876234 58327614 26318457 68172 453 23541867 38527416 65721843 13487562 35412876 34781256 35867142 51832674 7241 8536 25476183 56732184 24817653 46823175 74163852 48172635 73681542 31827546 764 58132 61472583 34278156 86512437 64587123 65218743 64132857 48167325 27581463 74 523816 43267815 75182346 53176824 25836147 51827364 75481362 12634578 25618347 7 6814532 42358671 26341587 23854167 26578431 64521783 81345627 16387452 67821453 13548762 37512486 83472561 35481726 63581427 34567812 47623815 35186742 57132864 73218456 38167452 72541836 28576413 35671842 12486537 25417863 24681753 6741852 3 75463182 53627184 74816352 43872165 24518637 87365421 74381652 23185467 576413 28 73658412 76145832 73421568 35478216 18654372 83612547 32178546 86451237 62487 513 16527438 64518273 36418572 65432187 52376184 64813257 42867135 26781543 6183 2547 27458163 71423586 64328157 87513462 74582136 75318246 32581476 24536817 463 72815 25183647 56127834 87543621 31265784 17234658 12563478 17685324 73614852 54 236718 47258361 78514362 42635871 28641357 52381674 26354817 72654318 23678541 3 8712546 26457831 68421573 82145367 25478361 81634527 15687342 26784531 41357628 16348572 13754862 78345612 86372451 62718453 83547261 62381547 21876543 63458127 31467582 24768153 83517426 34586172 35718642 65481237 17324568 63814527 7324158 6 72854136 73568421 34571682 81245376 13286457 36871452 12548637 26517483 824675 31 25481673 28136457 67541823 78563412 25361847 17483526 75416832 12456378 68734 215 82765341 87436521 82314675 26385147 45763281 52741638 21485637 57364128 7135 8642 47618325 73645182 27345681 76321458 61287453 73542168 31578426 17854632 745 21638 18365472 84312657 73215468 58642371 83651427 86245137 21654387 13627548 37 281546 16452738 37618452 78123456 36541872 68532417 75231846 16482573 65413827 6 4281357 34518762 82675431 36185472 26758413 27145863 26431578 65428317 18754623 86713542 63128547 87451362 73482516 17532468 74518326 71863542 32458176 21436587 74638152 82516473 24583167 48756213 82743561 63127845 38165274 85643271 3172658 4 15734268 61254783 17263548 81763245 12785634 25841637 17368524 75314682 514362 78 16385274 54723618 46758231 17853624 34268715 47235681 42863571 85236741 57281 364 71845362 52638174 71254638 14587632 72365418 24378651 13875462 52648317 2365 7481 26845731 76354128 48213675 72543618 82134657 81563427 82675314 23684751 541 36287 42157368 27584361 41635728 17648352 51378624 16354782 15427368 */