Новичок
Профиль
Группа: Участник
Сообщений: 1
Регистрация: 6.12.2009
Репутация: нет
Всего: нет
|
Тема, конечно уже старая, но раз уж я сделала, то напишу. У меня получилось 4 способа разместить 10 магараджей на доске 10*10. Вот код программы: | Код |
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
#define FREE_CELL -1
#define MAGARADJA_CELL 1
#define INACCESSIBLE_CELL 0
struct OnePlacement
{
int *i;
int *j;
int len;
};
struct OnePlacement * Placements;
int Number;
void PrintOnePlacement(struct OnePlacement op)
{
int i;
for (i=0; i< op.len; ++i)
{
printf("%2d x %2d\n", op.i[i], op.j[i]);
}
}
/* Считать значение параметра Param из файла======================*/
int ReadParamFromFile(char Param)
{
int res;
char str[100];
int len;
int pos1;
int pos2;
int col;
int j;
char* buf ;
FILE* pFile = fopen("D:\\magaradja.in", "r");
res = 10;
while ( !feof(pFile) )
{
fgets(str, 100, pFile);
len = strlen(str);
if (len > 1)
{
int i = 0;
while (str[i] == ' ' && i<len)
++i;
if (str[i] != '#')
{
// Если буква с которой начинается строка совпадает с названием параметра.
// Находим часть, которая после знака равно и преобразуем ее к int
if (str[i] == Param)
{
while (str[i] != '=') ++i;
++i;
while (str[i] == ' ') ++i;
pos1 = i;
while (str[i]<='9' && str[i] >= '0')
++i;
pos2 = i-1;
col = pos2-pos1+1;
buf = (char*)calloc(col, sizeof(char));
for (j = 0; j < col; ++j)
buf[j] = str[pos1 + j];
res = atoi(buf);
}
}
}
}
fclose(pFile);
return res;
}
/*================================================================*/
/*================================================================*/
int IsIJInOnePlacement(int i_mag, int j_mag, struct OnePlacement op)
{
int i, j;
int res;
if (op.len == NULL) return 0;
res = 0;
for (i=0; i < op.len; ++i)
{
if ( op.i[i] == i_mag && op.j[i] == j_mag)
res = 1;
}
return res;
}
/*================================================================*/
/*================================================================*/
int IsEqual(struct OnePlacement op1, struct OnePlacement op2)
{
int i, j;
if (op1.len == NULL) return 0;
if (op2.len == NULL) return 0;
if (op1.len <= 0) return 0;
if (op2.len <= 0) return 0;
if (op1.len != op2.len) return 0;
for (i=0; i < op1.len; ++i)
{
if ( !IsIJInOnePlacement(op1.i[i], op1.j[i], op2))
return 0;
}
return 1;
}
/*================================================================*/
/*================================================================*/
int IsInThePlacements(struct OnePlacement op)
{
int i;
if (op.len == NULL) return 0;
if (op.len <= 0) return 0;
for (i=0; i<Number; ++i)
{
if (IsEqual(Placements[i], op))
return 1;
}
return 0;
}
/*================================================================*/
/* Записываем в матрицу нули, там где точно нельзя будет поставить
магараджу, если новая магараджа ставится в ячейку [i_mgr,j_mgr] */
void SetInaccesibleCells(int **Matr, int M, int i_mgr, int j_mgr)
{
int i;
int j;
*(*(Matr +i_mgr) +j_mgr) = MAGARADJA_CELL;
// вертикальная линия
for (i = 0; i < M; ++i)
{
if (i != i_mgr)
if (*(*(Matr +i) +j_mgr) == FREE_CELL)
*(*(Matr +i) +j_mgr) = INACCESSIBLE_CELL;
}
// горизонтальная линия
for (j = 0; j < M; ++j)
{
if (j != j_mgr)
if ( *(*(Matr +i_mgr) +j) == FREE_CELL)
*(*(Matr +i_mgr) +j) = INACCESSIBLE_CELL;
}
// параллельно главной диагонали вверх
i = i_mgr-1;
j = j_mgr-1;
while (i>=0 && j>=0)
{
if ( *(*(Matr +i) +j) == FREE_CELL)
*(*(Matr +i) +j) = INACCESSIBLE_CELL;
--i;
--j;
}
// параллельно главной диагонали вниз
i = i_mgr+1;
j = j_mgr+1;
while (i<M && j<M)
{
if ( *(*(Matr +i) +j) == FREE_CELL)
*(*(Matr +i) +j) = INACCESSIBLE_CELL;
++i;
++j;
}
// параллельно побочной диагонали вверх
i = i_mgr-1;
j = j_mgr+1;
while (i>=0 && j<M)
{
if ( *(*(Matr +i) +j) == FREE_CELL)
*(*(Matr +i) +j) = INACCESSIBLE_CELL;
--i;
++j;
}
// параллельно побочной диагонали вниз
i = i_mgr+1;
j = j_mgr-1;
while (i<M && j>=0)
{
if ( *(*(Matr +i) +j) == FREE_CELL)
*(*(Matr +i) +j) = INACCESSIBLE_CELL;
++i;
--j;
}
// ход конем
i = i_mgr - 2;
j = j_mgr - 1;
if (i >= 0 && j >= 0)
if ( *(*(Matr +i) +j) == FREE_CELL)
*(*(Matr +i) +j) = INACCESSIBLE_CELL;
i = i_mgr - 2;
j = j_mgr + 1;
if (i >= 0 && j < M)
if ( *(*(Matr +i) +j) == FREE_CELL)
*(*(Matr +i) +j) = INACCESSIBLE_CELL;
i = i_mgr - 1;
j = j_mgr + 2;
if (i >= 0 && j < M)
if ( *(*(Matr +i) +j) == FREE_CELL)
*(*(Matr +i) +j) = INACCESSIBLE_CELL;
i = i_mgr + 1;
j = j_mgr + 2;
if (i < M && j < M)
if ( *(*(Matr +i) +j) == FREE_CELL)
*(*(Matr +i) +j) = INACCESSIBLE_CELL;
i = i_mgr + 2;
j = j_mgr + 1;
if (i < M && j < M)
if ( *(*(Matr +i) +j) == FREE_CELL)
*(*(Matr +i) +j) = INACCESSIBLE_CELL;
i = i_mgr + 2;
j = j_mgr - 1;
if (i < M && j >= 0)
if ( *(*(Matr +i) +j) == FREE_CELL)
*(*(Matr +i) +j) = INACCESSIBLE_CELL;
i = i_mgr + 1;
j = j_mgr - 2;
if (i < M && j >= 0)
if ( *(*(Matr +i) +j) == FREE_CELL)
*(*(Matr +i) +j) = INACCESSIBLE_CELL;
i = i_mgr - 1;
j = j_mgr - 2;
if (i >= 0 && j >= 0)
if ( *(*(Matr +i) +j) == FREE_CELL)
*(*(Matr +i) +j) = INACCESSIBLE_CELL;
}
/*================================================================*/
/*================================================================*/
void PrintDoska(int** Matr, int M)
{
int i,j;
for (i=0; i<M; ++i)
{
for (j=0; j<M; ++j)
{
printf("%3d", Matr[i][j]);
}
printf("\n");
}
printf("\n");
}
/*================================================================*/
/*=================================================================*/
int ** NewDoskaCopy(int ** MainDoska, int M)
{
int ** doska;
int i,j;
doska = (int **)calloc(M, sizeof(int));
for (i=0; i< M ; ++i)
{
doska[i] = (int *)calloc(M, sizeof(int));
for (j=0; j<M; ++j)
doska[i][j] = MainDoska[i][j];
}
return doska;
}
/*=================================================================*/
/*=================================================================*/
void FindFromPosition(int i_pos, int j_pos, int ** MainDoska, int num, int K, int M, int *count)
{
int i, j, i1;
int rab;
int ** doska;
struct OnePlacement op;
*count = *count + 1;
rab = 0;
num = num +1;
//printf("%d-i mag: %d %d\n",num, i_pos, j_pos);
if (num>=K)
{
op.len = num;
op.i = (int *)calloc(op.len, sizeof(int));
op.j = (int *)calloc(op.len, sizeof(int));
i1=0;
for (i=0;i<M;++i)
{
for (j=0;j<M; ++j)
{
if (MainDoska[i][j] == MAGARADJA_CELL)
{
op.i[i1] = i;
op.j[i1] = j;
i1++;
}
}
}
op.i[i1] = i_pos;
op.j[i1] = j_pos;
if (IsInThePlacements(op) == 0)
{
if (Number == 0 )
{
//Placements = (OnePlacement *)calloc(Number, sizeof(op));
Placements=(struct OnePlacement * )malloc(sizeof(struct OnePlacement));
}
else
{
Placements = realloc(Placements, (Number+1)*sizeof(struct OnePlacement));
}
Placements[Number ].len = op.len;
Placements[Number].i = (int *)calloc(op.len, sizeof(int));
Placements[Number].j = (int *)calloc(op.len, sizeof(int));
for (i=0; i<op.len; ++i)
{
Placements[Number].i[i] = op.i[i];
Placements[Number].j[i] = op.j[i];
}
Number = Number + 1;
free(op.i);
free(op.j);
}
return;
}
SetInaccesibleCells(MainDoska, M, i_pos, j_pos);
i= i_pos;
j= j_pos+1;
while (i < M)
{
while (j < M)
{
if (MainDoska[i][j]== FREE_CELL)
{
doska = NewDoskaCopy(MainDoska, M);
FindFromPosition(i,j,doska,num, K, M, count);
free(doska);
}
++j;
}
j=0;
++i;
}
}
/*=================================================================*/
int main()
{
int i, j, kol;
int ** Doska;
int ** Doska1;
int num;
int count;
int M, K;
count = 0;
M = ReadParamFromFile('M');
K = ReadParamFromFile('K');
M=10;
K=10;
Doska = (int **)calloc(M, sizeof(int));
for (i=0; i< M ; ++i)
{
Doska[i] = (int *)calloc(M, sizeof(int));
for (j=0; j<M; ++j)
{
Doska[i][j] = FREE_CELL;
}
}
i=0;
j=0;
//PrintDoska(Doska, M);
num = 0;
for (i=0; i< M; ++i)
{
for (j=0; j<M; ++j)
{
Doska1 = NewDoskaCopy(Doska, M);
FindFromPosition(i,j, Doska1, num, K,M, &count);
}
}
for (i=0; i<Number; ++i)
{
PrintOnePlacement(Placements[i]);
printf("\n");
}
getchar();
return 1;
}
|
Вот способы: 0 x 2 1 x 5 2 x 8 3 x 0 4 x 3 5 x 6 6 x 9 7 x 1 8 x 4 9 x 7 0 x 3 1 x 7 2 x 0 3 x 4 4 x 8 5 x 1 6 x 5 7 x 9 8 x 2 9 x 6 0 x 6 1 x 2 2 x 9 3 x 5 4 x 1 5 x 8 6 x 4 7 x 0 8 x 7 9 x 3 0 x 7 1 x 4 2 x 1 3 x 9 4 x 6 5 x 3 6 x 0 7 x 8 8 x 5 9 x 2 Это сообщение отредактировал(а) yomilagro - 6.12.2009, 23:57 |
Магараджи 
Загрузка ...
