Навскидку решив обойтись без эвристической функции, так как ее написание потребовало бы больше времени, написал решение за два часаMagic Squares
Following the success of the magic cube, Mr. Rubik invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares (see Figure 3).
1 2 3 4
8 7 6 5
Figure 3: Initial configuration
In this task we consider the version where each square has a different colour. Colours are denoted by the first 8 positive integers (see Figure 3). A sheet configuration is given by the sequence of colours obtained by reading the colours of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of Figure 3 is given by the sequence
(1,2,3,4,5,6,7,8). This configuration is the initial configuration.
Three basic transformations, identified by the letters 'A', 'B' and 'C', can be applied to a sheet:
'A': exchange the top and bottom row,
'B': single right circular shifting of the rectangle,
'C': single clockwise rotation of the middle four squares.
All configurations are available using the three basic transformations.
Figure 4: Basic transformations
The effects of the basic transformations are described in Figure 4. Numbers outside the squares denote square positions. If a square in position p contains number i, it means that after applying the transformation, the square whose position was i before the transformation moves to position p.
You are to write a program that computes a sequence of basic transformations that transforms the initial configuration of Figure 3 to a specific target configuration (Subtask A). Two extra points will be given for the solution if the length of the transformation sequence does not exceed 300 (Subtask.
Input Data
The file INPUT.TXT contains 8 positive integers in the first line, the description of the target configuration.
Output Data
On the first line of file OUTPUT.TXT your program must write the length L of the transformation sequence. On the following L lines it must write the sequence of identifiers of basic transformations, one letter in the first position of each line.
Tool
MTOOL.EXE is a program in the task directory that lets you play with the magic squares. By executing "mtool input.txt output.txt" you can experiment with the target configuration and the sequence of transformations.
Example Input and Output
INPUT.TXT OUTPUT.TXT
2 6 8 4 5 7 3 1 7
B C A B C C B
Figure 5: Example Input and Output
вот мой резалт
// squares.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <string.h>
#define DEEPLEVEL 25
#define OPTIMIZELEVEL 2
int iData[8]; //digit data
static int iTarget[8];
static char cSolution[25];
static char *pz;
FILE *fli,*flout;
int iMutationConst(char cType, int iDataArr [], int iDeepLevel);
bool bCheckMutation (int iDataArr[]);
void vOptimizeS ();
int main(int argc, char *argv[])
{
int iData [8] = {1,2,3,4,5,6,7,8};//initial Configuration
int len; //lenght of Solution
pz = cSolution; // pointer to solution string
/// Parameters Control
if (argc <3){
printf ("Two parameters required. \n");
exit(1);
}
// Loading Target Array and control input data
fli=fopen(argv[1],"r");
for (int i=0; i<8; i++)
if(fscanf (fli," %d",&iTarget[i])==EOF){
printf ("Incorrect parameter. \n");
exit(1);
}
//If the target configuration the same ad initial
if (bCheckMutation(iData)){
printf ("Target the same as beginning. \n");
exit(1);
}
// beginning
if (iMutationConst('A', iData , 1)==1){
}else
if (iMutationConst('B', iData , 1)==1){
}else
if (iMutationConst('C', iData , 1)==1){
}
//Optimize solution
for (int i=0; i<OPTIMIZELEVEL; i++)
vOptimizeS();
len =strlen(cSolution);
//Print out solution into file
flout = fopen(argv[2],"w");
fprintf (flout,"%d",len);
while (len>=0){
fprintf (flout,"%c\n",cSolution[len]);
len--;
}
fclose(fli);
fclose(flout);
return 0;
}
int iMutationConst(char cType, int iDataArr [], int iDeepLevel){
int iD [8], iDt[8];//Array for data which sqves in recursive operations
if (cType=='A'){
//A movement
iD[0]= iDataArr[7];
iD[1]= iDataArr[6];
iD[2]= iDataArr[5];
iD[3]= iDataArr[4];
iD[4]= iDataArr[3];
iD[5]= iDataArr[2];
iD[6]= iDataArr[1];
iD[7]= iDataArr[0];
}
else if (cType=='B'){
// B Movement
iD[0]= iDataArr[3];
iD[1]= iDataArr[0];
iD[2]= iDataArr[1];
iD[3]= iDataArr[2];
iD[4]= iDataArr[5];
iD[5]= iDataArr[6];
iD[6]= iDataArr[7];
iD[7]= iDataArr[4];
}
else {
// C Movement
iD[0]= iDataArr[0];
iD[1]= iDataArr[6];
iD[2]= iDataArr[1];
iD[3]= iDataArr[3];
iD[4]= iDataArr[4];
iD[5]= iDataArr[2];
iD[6]= iDataArr[5];
iD[7]= iDataArr[7];
}
// Save data for back turns
for (int i=0; i<8;i++)
iDt[i]= iD[i];
//Check if finish configuration considered
if (bCheckMutation (iD)) {
*pz=cType;
pz++;
return 1;
}
else if (iDeepLevel >= DEEPLEVEL)
return 0;
else {
iDeepLevel++;
if (cType != 'A') // exclude AA transformation
if (iMutationConst('A', iD , iDeepLevel)==1){//recursive operation for next mutation
*pz=cType; //if target considered save turn
pz++;
return 1;
}
else
for (int i=0; i<8;i++)//Turn back
iD[i]= iDt[i];
if (iMutationConst('B', iD , iDeepLevel)==1){//recursive operation for next mutation
*pz=cType; //if target considered save turn
pz++;
return 1;
}
else
for (int i=0; i<8;i++)
iD[i]= iDt[i];
if (iMutationConst('C', iD , iDeepLevel)==1){//recursive operation for next mutation
*pz=cType; //if target considered save turn
pz++;
return 1;
}
else
for (int i=0; i<8;i++)
iD[i]= iDt[i];
return 0;
}
}
bool bCheckMutation (int iDataArr[]){
if ((iDataArr[0]==iTarget[0]) && (iDataArr[1]==iTarget[1]) && (iDataArr[2]==iTarget[2]) && (iDataArr[3]==iTarget[3]) && (iDataArr[4]==iTarget[4]) && (iDataArr[5]==iTarget[5]) && (iDataArr[6]==iTarget[6]) && (iDataArr[7]==iTarget[7]))
return true;
else
return false;
}
void vOptimizeS(){
///Optimize function removes ABA to B and BBBB mutations
char cTemp [25];
char *pAT;
int len;
pAT = cTemp;
len =strlen(cSolution);
len--;
while (len>=0){
if ((cSolution[len]=='A') && (cSolution[len-1]=='B') && (cSolution[len-2]=='A'))
{
*pAT='B';
pAT++;
len-=3;
}
else if ((cSolution[len]=='B') && (cSolution[len-1]=='B') && (cSolution[len-2]=='B')&& (cSolution[len-3]=='B'))
{
len-=4;
}
else
{
*pAT=cSolution[len];
pAT++;
len--;
}
}
*pAT=0;
for (int i=0; i<(int)strlen(cTemp); i++)
cSolution[i]=cTemp[i];
cSolution[strlen(cTemp)]=0;
}
Немного кривоват но все работает
При желании код можно оптимизировать но лень и не в этом была цель
Сообщение изменено: Ничего не боится (04 мая 2005 - 13:25 )
