Magic SquaresIOI’96
Following the success of the magic cube, Mr. Rubik invented its planarversion, called magic squares. This is a sheet composed of 8 equal-sizedsquares:
1234
8765
In this task we consider the version where each square has a differentcolor. Colors are denoted by the first 8 positive integers. A sheetconfiguration is given by the sequence of colors obtained by readingthe colors of the squares starting at the upper left corner and goingin clockwise direction. For instance, the configuration of Figure3 is given by the sequence (1,2,3,4,5,6,7,8). This configurationis the initial configuration.
Three basic transformations, identified by the letters `A’, `B’ and`C’, can be applied to a sheet:
Below is a demonstration of applying the transformations tothe initial squares given above:
A:
8765
1234
B:
4123
5876
C:
1724
8635
All possible configurations are available using the three basictransformations.
You are to write a program that computes a minimal sequence of basictransformations that transforms the initial configuration above to aspecific target configuration.
PROGRAM NAME: msquareINPUT FORMAT
A single line with eight space-separated integers (a permutation of(1..8)) that are the target configuration.
SAMPLE INPUT (file msquare.in) 2 6 8 4 5 7 3 1 OUTPUT FORMAT
Line 1:A single integer that is the lengthof the shortest transformation sequence.
Line 2:The lexically earliest string of transformations expressedas a string of characters, 60 per line except possibly the last line.
SAMPLE OUTPUT (file msquare.out)7BCABCCB分析
这道题目比较麻烦，很久没写这样长的代码了。注意2点：代码中记录序列必须用头插法，，类似于从树枝到根的逆序，想想为什么不能从根到树枝；哈希的映射；当变换次数为0时，需要打印一个换行符。
通过代码Executing… Test 1: TEST OK [0.005 secs, 4052 KB] Test 2: TEST OK [0.005 secs, 4048 KB] Test 3: TEST OK [0.008 secs, 4052 KB] Test 4: TEST OK [0.011 secs, 4052 KB] Test 5: TEST OK [0.041 secs, 4180 KB] Test 6: TEST OK [0.032 secs, 4312 KB] Test 7: TEST OK [0.057 secs, 4580 KB] Test 8: TEST OK [0.081 secs, 4580 KB]All tests OK.
/*ID: c1033311LANG: C++TASK: msquare*/#include<stdio.h>#include<string.h>#include<stdlib.h>#define LEN 40320typedef struct Node{char ch;struct Node *next;}Node;/**************列队中元素**************/typedef struct{char str[8];int cnt;Node *start; //使用头插法}State;/**************阶乘函数**************/int A(int n){int i,sum=1;for(i=2;i<=n;++i)sum*=i;return sum;}/**************状态与整数一一对应，就是大小顺序值，从0开始**************/int hash(char *str){int i,j,a[9]={0};int sum=0;for(i=0;i<8;++i) //每一位{int n=0;for(j=1;j<str[i]-'0';++j)if(a[j]==0)++n;sum+=n*A(7-i);a[str[i]-'0']=1;}return sum;}/**************将字符串转化为整形**************/int toInt(char *str){int n;sscanf(str,"%d",&n);return n;}/**************转换函数**************/void change(char s[8],char *str,int n){int i;switch(n){case 0:for(i=0;i<8;++i)s[i]=str[7-i];break; case 1:s[0]=str[3];for(i=1;i<=3;++i)s[i]=str[i-1];for(;i<=6;++i)s[i]=str[i+1];s[7]=str[4];break; case 2:s[0]=str[0];s[1]=str[6];s[2]=str[1];s[3]=str[3];s[4]=str[4];s[5]=str[2];s[6]=str[5];s[7]=str[7];break; }}int main(){FILE *fin=fopen("msquare.in","r");FILE *fout=fopen("msquare.out","w");char ans[8];int i,t;State queue[LEN];int front=0,tail=0;bool vis[LEN]={0};//输入数据for(i=0;i<8;++i){fscanf(fin,"%d",&t);ans[i]='0'+t;}//初始化将初始状态加入队列memcpy(queue[tail].str,"12345678",8);queue[tail].cnt=0;queue[tail].start=NULL;vis[hash(queue[tail].str)]=true;++tail;while(front<=tail){//找到目标状态if(toInt(queue[front].str)==toInt(ans)){char *s=(char*)malloc((queue[front].cnt)*sizeof(char));fprintf(fout,"%d",queue[front].cnt);for(i=queue[front].cnt-1;queue[front].start!=NULL;–i) //打印序列{s[i]=queue[front].start->ch;queue[front].start=queue[front].start->next;}for(i=0;i<queue[front].cnt;++i)if(i%60==0)fprintf(fout,"\n%c",s[i]);elsefprintf(fout,"%c",s[i]);if(queue[front].cnt==0)fprintf(fout,"\n");fprintf(fout,"\n");break;}for(i=0;i<3;++i){char s[8];change(s,queue[front].str,i);if(vis[hash(s)]==false){vis[hash(s)]=true;memcpy(queue[tail].str,s,8);queue[tail].cnt=queue[front].cnt+1;Node *node=(Node*)malloc(sizeof(Node));node->ch='A'+i;node->next=queue[front].start;queue[tail].start=node;++tail;}}//end forfront++; }return 0;}
泪，一种痛苦的雨滴，不知从什么时候开始已在我的世界下个不停。
