Leksus
Зарегистрирован: 12.01.2005
Сообщения: 4
|
 Добавлено: Вт Мар 08 2005 22:32 Заголовок сообщения: Ваше мнение |
 |
|
Ваши замечания присылайте по адресу Leksus83@netman.ru
/* программа обхода шахматной доски конем с использованием эвристики
Конь обходит пустую шахматную доску побывав в каждой клетке только один раз
по завершению каждого обхода начинается следующий обход но с другой клетки */
| Код: | #include<stdio.h>
int CheckAcces(const int,int,const int[][8],const int [][8], const int,const int, const int,const int, const int[],const int[]);
int virtStep(int,int,int[][8],int[][8],int[],const int[], const int[] );
int check(const int,const int,const int,const int[],const int[],const int[][8]);
void PrintfArray(const int[][8]);/*выводит на экран массив*/
void ModifyArray(int[][8], const int[][8],const int[],const int[]);/*модификация массива показателей досттупности шахматных клеток*/
int main(){
int currentRow=0,currentColumn=0; /*текущее положение коня на шахматной доске*/
int accessibility[8][8]={0}; /* массив показателей доступности клеток*/
const int horizontal[8]={ 2, 1,-1,-2,-2,-1,1,2}; /*перемещение коня по горизонтали*/
const int vertical[8]= {-1,-2,-2,-1, 1, 2,2,1}; /*перемещение коня по вертикали*/
for(int CR=0;CR<=7;CR++)for(int CC=0;CC<=7;CC++){/* начало обхода конем из различных клеток*/
int board[8][8]={0};/*шахматная доска, инициализированна нулями*/
currentRow=CR;/* присвоение следующего начального положения коня*/
currentColumn=CC;
printf("currentRow=%d;currentColumn%d;\n", currentRow, currentColumn);
for(int i=1;i<=64;i++){
if(i==1){board[currentRow][currentColumn]=1;continue;}
ModifyArray(accessibility, board, horizontal, vertical); //модификация показателей доступности клеток,он равен количеству клеток из которых доступна эта клетка
//if(i<10/*||i==63||i==60*/){PrintfArray(accessibility);PrintfArray(board);printf("currentRow=%d;currentColumn%d;\n", currentRow, currentColumn);}// выводит первоночальное состояние показателей доступности клеток до начала обхода
int first=0,midlRow,midlColumn;
for(int move=0;move<=7;move++){// перебор возможных ходов
if(check(move,currentRow,currentColumn,horizontal, vertical,board)) {
if(first==0){midlRow=currentRow+horizontal[move];midlColumn=currentColumn+vertic
al[move];first=1;continue;}
if(CheckAcces(i,move,accessibility,board,midlRow,midlColumn,currentRow,currentCo
lumn,horizontal,vertical)){midlRow=currentRow+horizontal[move];midlColumn=curren
tColumn+vertical[move];}
} }
currentRow=midlRow;
currentColumn=midlColumn;
//printf("step=%d; currentRow=%d;currentColumn=%d; ", i, currentRow,currentColumn);
//printf("accessibility[%d][%d]=%d\n\n", currentRow,currentColumn,accessibility[currentRow][currentColumn]);
if( board[currentRow][currentColumn]!=0)break;
else{ board[currentRow][currentColumn]=i;
/*printf("BAS array modification\n"); PrintfArray(board);*/}
}
printf("\n");
PrintfArray(board);
int eror=0;
for(int r=0;r<=7;r++)for(int c=0;c<=7;c++)if(board[r][c]==0)eror++;
if(eror>0){printf(" steps are not complit start point is [%d][%d]\n", CR,CC);
getchar();
getchar();
}
else printf("Ok\n");
printf("\n\n\n");
//PrintfArray(accessibility);
}
getchar();
getchar();
}
void PrintfArray(const int a[][8]){
printf("\n");
for(int i=0;i<=7;i++){
for(int j=0;j<=7;j++)
printf("%-2d ",a[i][j]);
printf("\n");
}
printf("\n");
//getchar();
//getchar();
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
void ModifyArray(int acces[][8],const int Board[][8],const int Horizontal[],const int Vertical[])
{
//printf("In function of modification");
for(int i=0;i<=7;i++)for(int j=0;j<=7;j++)acces[i][j]=0;
//PrintfArray(acces);
//PrintfArray(Board);
for(int CRow=0;CRow<=7;CRow++)for(int CCol=0;CCol<=7;CCol++)
if(Board[CRow][CCol]==0)
for(int move=0;move<=7;move++)
if(check(move,CRow,CCol,Horizontal,Vertical,Board))acces[CRow][CCol]++;
//PrintfArray(acces);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
int check(const int m,const int CR,const int CC,const int Hor[],const int Ver[],const int B[][8]){
if(((8>(CC+Ver[m]))&&(8>(CR+Hor[m])))&&(((CR+Hor[m])>=0)&&((CC+Ver[m])>=0))&&(B[CR+Hor[m]][CC+Ver[m]]==0))return 1;
else return 0;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////
int CheckAcces(int const n,int m,const int acc[][8],const int bOARD[][8], const int mr,const int mc, const int cr,const int cc, const int horiz[],const int vert[]){
if(acc[mr][mc]==acc[cr+horiz[m]][cc+vert[m]]){
int CrAndCc[2]={cr+horiz[m],cc+vert[m]},MrAndMc[2]={mr,mc};
int MrMc=1,CrCc=0;
int CAcc[8][8],CBOARD[8][8],MAcc[8][8],MBOARD[8][8];
for(int i=0;i<=7;i++)for(int j=0;j<=7;j++)CAcc[i][j]=0;
for(int i=0;i<=7;i++)for(int j=0;j<=7;j++)MAcc[i][j]=0;
for(int i=0;i<=7;i++)for(int j=0;j<=7;j++)CBOARD[i][j]=bOARD[i][j];
for(int i=0;i<=7;i++)for(int j=0;j<=7;j++)MBOARD[i][j]=bOARD[i][j];
int M=acc[mr][mc],C=acc[cr+horiz[m]][cc+vert[m]];
/* printf("Befor :M=%d [%d][%d] C=%d [%d][%d] Step=0 \n",M,mr,mc,C,cr+horiz[m],cc+vert[m]);
printf("////////////////////////CURENT COPY////////////////////////\n//////////////////////////");
PrintfArray(CBOARD);
PrintfArray(CAcc);
printf("////////////////////////MIDL COPY//////////////////////////");
PrintfArray(MBOARD);
PrintfArray(MAcc);
getchar();
getchar();
*/
//printf("Befor :M=%d [%d][%d] C=%d [%d][%d] Step=0 \n",M,mr,mc,C,cr+horiz[m],cc+vert[m]);
int step=0, first=1;
for(int g=n;g<=n+2;g++){
if(first){
MBOARD[MrAndMc[0]][MrAndMc[1]]=g;
CBOARD[CrAndCc[0]][CrAndCc[1]]=g;
//printf("MODIFY\n");
ModifyArray(CAcc,CBOARD , horiz, vert);
ModifyArray(MAcc, MBOARD, horiz, vert);
first=0;
continue;}
/*
printf("////////////////////////CURENT afte step has being don////////////////////////\n//////////////////////////");
PrintfArray(CBOARD);
PrintfArray(CAcc);
printf("////////////////////////MIDL afte step has being don//////////////////////////");
PrintfArray(MBOARD);
PrintfArray(MAcc);
getchar();
getchar();*/
M=virtStep(MrMc,g,MAcc,MBOARD,MrAndMc,horiz,vert);
//printf(" After :M=%d [%d][%d];C=%d [%d][%d]; Step=%d\n",M,MrAndMc[0],MrAndMc[1],C,CrAndCc[0],CrAndCc[1],step);
//getchar();
//getchar();
C=virtStep(CrCc,g,CAcc,CBOARD,CrAndCc,horiz,vert);
//printf(" After :M=%d [%d][%d];C=%d [%d][%d]; Step=%d\n",M,MrAndMc[0],MrAndMc[1],C,CrAndCc[0],CrAndCc[1],step);
//getchar();
//getchar();
if(M>C)return 1;
if(M==C==0)return 0;
if((M==C)&&(g==g+n))return 0;
if(M<C)return 0;
}
}
if(acc[mr][mc]>acc[cr+horiz[m]][cc+vert[m]])return 1;
else return 0;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
int virtStep(int ch,int n,int ACC[][8],int Desk[][8],int CRandCC[],const int h[],const int v[]){
int first=0,mR=0,mC=0;
ModifyArray(ACC, Desk, h, v);
//if(ch==0)printf(" CURENT in \n");
//if(ch==1)printf(" MIDL in \n");
//PrintfArray(Desk);
//PrintfArray(ACC);
for(int move=0;move<=7;move++){// перебор возможных ходов
if(check(move,CRandCC[0],CRandCC[1],h,v,Desk)){
if(first==0){mR=CRandCC[0]+h[move];mC=CRandCC[1]+v[move];first=1;continue;}
//printf("mR=%d;mC=%d; CRandCC[0]+h[move]=%d;CRandCC[1]+v[move]=%d;\n",mR,mC,CRandCC[0]+h[move],CRandCC[1]+v[move]);
if(ACC[mR][mC]& gt;ACC[CRandCC[0]+h[move]][CRandCC[1]+v[move]]){mR=CRandCC[0]+h[move];mC=CRandCC
[1]+v[move];}
}
}
/*if(ch==0)printf(" CURENT \n");
if(ch==1)printf(" MIDL \n");*/
//printf("mR=%d; mC=%d;\n", mR, mC);
//printf("Befor CRAndCC[0]=%d,CRndCC[1]=%d\n",CRandCC[0],CRandCC[1]);
CRandCC[0]=mR;
CRandCC[1]=mC;
// printf("After CRAndCC[0]=%d,CRndCC[1]=%d\n",CRandCC[0],CRandCC[1]);
if( Desk[mR][mC]!=0)return 0;
else Desk[mR][mC]=n;
//if(ch==0)printf(" CURENT in func \n");
//if(ch==1)printf(" MIDL in func \n");
//PrintfArray(Desk);
//PrintfArray(ACC);
return ACC[mR][mC];
}
//////////////////////////////////////////////////////////////////////////////////////////////////////// |
|
|
FAQ 
Поиск 
Пользователи 
Группы
Регистрация
Профиль 
Войти и проверить личные сообщения 
Вход 
