Решение для задачи #include #include #include




Yüklə 101.86 Kb.
tarix28.02.2016
ölçüsü101.86 Kb.
Текст программы — решение для задачи 1.
#include

#include

#include

#include

#include

#include

#include

#include

#include

//

int get_x(char );

int get_y(char );

int _get(int, char *, int);

int er,d1,d2;

//структура, определяющая состояние клетки

struct chess {

//координаты клетки

int x;

int y;

int pr;//признак принадлежности к группе

int k; //количество соседей

};

int t,s;

//массив доски 0 - пусто, 1 - шашка

//данный массив используется только

//для анализа ввода данных (наличие

//совпадающих координат)

int chs[8][8]={

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

};

char * line;

//массив клеток доски

chess chss[64];

chess cg1, cg2;

int main()

{

int i,j,h,nm=0;

//начальная инициализация массива

for(int i=0; i<64; i++){

chss[i].x=0;

chss[i].y=0;

chss[i].pr=-1;

chss[i].k=0;

};

//переменная для ввода строки

line = (char*)malloc(1000);

//расположение шашек

if(fgets(line,1000,stdin)==NULL){

fprintf(stdout,"Error!\n");

goto _end;

}

//как расставлены шашки

er=_get(64,line,1);

if(er!=0) {

fprintf(stdout,"Error!\n");

goto _end;

}

//анализ входных данных

//(t-глобальная переменная, содержащая //количество шашек

if(t==0) {

fprintf(stdout,"No parameters\n");

goto _end;

}

//распределяем по группам

for(i=0; i

if(chss[i].pr==-2)

{

chss[i].pr=nm;nm++;

}

//ищем соседей

for(j=i+1; j

{

//проверяем не сосед ли

if(

(chss[i].x+1==chss[j].x&&chss[i].y==chss[j].y)||

(chss[i].x-1==chss[j].x&&chss[i].y==chss[j].y)||

(chss[i].x==chss[j].x&&chss[i].y+1==chss[j].y)||

(chss[i].x==chss[j].x&&chss[i].y-1==chss[j].y)

){

if(chss[j].pr==-2)

chss[j].pr=chss[i].pr;

else{

//не образовалась ли изолированная //группа

//если есть, то объединяем

for(d1=0;d1

{

if(chss[d1].pr==chss[i].pr)

chss[d1].pr=chss[j].pr;

}

}

//одна группа

chss[j].k++; //есть сосед

chss[i].k++; //есть сосед

}

}

}

//сортировка по номуру группы

for(i=0; i

for(j=0; j

if(chss[j].pr>chss[j+1].pr){

cg1=chss[j];

chss[j]=chss[j+1];

chss[j+1]=cg1;

}

}

}

//расчет периметров и вывод

d1=chss[0].pr;s=0;

for(i=0; i

if(d1==chss[i].pr) s=s+(4-chss[i].k);

else{

fprintf(stdout,"%d\n",s);

d1=chss[i].pr; s=4-chss[i].k;

}

}

//вывод последнего значения

fprintf(stdout,"%d\n",s);

//вывод пути

_end:

free(line);

return 0;

}

//получить n (max) координат

int _get(int n, char * s, int p)

{

int i,j=0,k=0,x1,y1;

int l = strlen(s);

t=0;

for(i=0; i

if(s[i]==' '){

if(!k)continue;

if(k==1)return -1;

}

if(s[i]<='h'&&s[i]>='a'){

if(k!=0)return -1;

k++;

x1=get_x(s[i]);

}

if(s[i]<='8'&&s[i]>='1'){

if(k!=1)return -1;

y1=get_y(s[i]);

k=0;

if(chs[x1][y1]!=0)return -1;

chs[x1][y1]=p;

chss[t].x=x1; chss[t].y=y1; chss[t].pr=-2;

t++; j++;

if(j==n)break;

}

}

return 0;

}

//получить значение x

int get_x(char c)

{

return (int)(c-'a');

}

//получить значение y

int get_y(char c)

{

return (int)(c-'1');

}
Текст программы — решение для задачи 2.
#include

#include

#include

#include

#include

#include

#include

#include

#include

//структура файла

//все шашки

//шашка, которая будет ходить

//пункт назначения

char get_x1(int );

char get_y1(int );

int get_x(char );

int get_y(char );

int _get(int, int *, int *, char *, int);

int rec(int , int, int);

void cop(int);

void step(int , int , int);

int zamur();

//

int xs,ys; //позиция шашки

int xp,yp; //пункт назначения

int lmm,lm,d,g,h;

//массив доски 0 - пусто, 1 - шашка, -1 -

//временная пометка, что шашка здесь //была

int chs[8][8]={

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

};

//массив для хранения текущего пути,

//пройденного шашкой

int mx[64]={};

int my[64]={};

//массив для хранения минимального

//количества шагов

int mx1[64]={};

int my1[64]={};

int i,j,er,i1,j1,lm1,ke;

char * line;

int main()

{

//инициализация массивов

for(i=0;i<64;i++){

mx[i]=0; my[i]=0;

mx1[i]=0; my1[i]=0;

}

line = (char*)malloc(1000);

//расположение шашек

if(fgets(line,1000,stdin)==NULL){

fprintf(stdout,"Error!\n");

goto _end;

}

//как расставлены шашки

er=_get(64,&i,&j,line,1);

if(er!=0){

fprintf(stdout,"Error!\n");

goto _end;

}

//шашка, которая ходит

if(fgets(line,1000,stdin)==NULL){

fprintf(stdout,"Error!\n");

goto _end;

}

i=-1; j=-1;

er=_get(1,&i,&j,line,-1);

if(er!=0||i<0||i>7||j<0||j>7){

fprintf(stdout,"Error!\n");

goto _end;

}

xs=i; ys=j;

//место, куда идти (принцесса)

if(fgets(line,1000,stdin)==NULL){

fprintf(stdout,"Error!\n");

goto _end;

}

i=-1; j=-1;

er=_get(1,&i,&j,line,0);

if(er!=0||i<0||i>7||j<0||j>7){

fprintf(stdout,"Error!\n");

goto _end;

}

xp=i; yp=j;

if(!zamur()){

fprintf(stdout,"No path!\n");

goto _end;

}

//поиск пути

lm1=abs(xs-xp)+abs(ys-yp);

ke=lm1;

if(xs==xp&&ys==yp){

fprintf(stdout,"No steps!\n");

}else{

_con:

//длины - lmm- текущий путь,

//lm - временный минимум

lmm=0;d=0; g=0; lm=lm1;

rec(xs,ys,1);

lmm=0;

rec(xs,ys,2);

lmm=0;

rec(xs,ys,3);

lmm=0;

rec(xs,ys,4);

if(d==0&&g==1) {

//повтор, если максимальным

//количеством шагов=14

//не удалось дойти

lm1=lm1+ke;

if(lm1<=28) goto _con;

}

if(d==0)fprintf(stdout,"No path!\n");

else{

fprintf(stdout,"%d\n",lm);

for(i=0; i

fprintf(stdout,"%c%c",get_x1(mx1[i]),get_y1(my1[i]));

}

fprintf(stdout,"\n");

}

}

//вывод пути

_end:

free(line);

return 0;

}

//рекурсивная функция поиска, четыре направления:

// 1 +x, 2 -x, 3 +y, 4 -y

int rec(int x, int y, int p)

{

h=0; int xs,ys;

xs=x; ys=y;

//пробуем сделать шаг

switch(p)

{

case 1:

if(x+1<=7){

if(chs[x+1][y]!=-1){

if(chs[x+1][y]!=1){

xs++;h=1; chs[xs][ys]=-1;

}else{

if(x+2<=7&&chs[x+2][y]!=1

&&chs[x+2][y]!=-1){

xs=xs+2; h=1;chs[xs][ys]=-1;

}

}

}

}

break;

case 2:

if(x-1>-1){

if(chs[x-1][y]!=-1){

if(chs[x-1][y]!=1){

xs--; h=1;chs[xs][ys]=-1;

}else{

if(x-2>-1&&chs[x-2][y]!=1

&&chs[x-2][y]!=-1){

xs=xs-2; h=1;chs[xs][ys]=-1;

}

}

}

}

break;

case 3:

if(y+1<=7){

if(chs[x][y+1]!=-1){

if(chs[x][y+1]!=1){

ys++; h=1;chs[xs][ys]=-1;

}else{

if(y+2<=7&&chs[x][y+2]!=1

&&chs[x][y+2]!=-1){

ys=ys+2; h=1;chs[xs][ys]=-1;

}

}

}

}

break;

case 4:

if(y-1>-1){

if(chs[x][y-1]!=-1){

if(chs[x][y-1]!=1){

ys--; h=1;chs[xs][ys]=-1;

}else{

if(y-2>-1&&chs[x][y-2]!=1

&&chs[x][y-2]!=-1){

ys=ys-2; h=1;chs[xs][ys]=-1;

}

}

}

}

break;

}

//корректируем длину (количество ша//гов)

if(h==1){

mx[lmm]=xs; my[lmm]=ys;

lmm++;

if(lmm>lm){

g=1; chs[xs][ys]=0; lmm--;

return 0;

}

if(xs==xp&&ys==yp){

d=1;

//если попали, то корректируем

//временный минимум и выходим

if(lmm<=lm){

lm=lmm;

cop(lm);

}

}else{

//продолжаем рекурсивно

rec(xs,ys,1); rec(xs,ys,2); rec(xs,ys,3); rec(xs,ys,4);

}

}else{

return 0;

}

chs[xs][ys]=0; lmm--;

return 0;

}

//получить n (max) координат

int _get(int n, int * x, int * y, char * s, int p)

{

int i,j=0,k=0,x1,y1;

int l = strlen(s);

for(i=0; i

{

if(s[i]==' ')

{

if(!k)continue;

if(k==1)return -1;

}

if(s[i]<='h'&&s[i]>='a')

{

if(k!=0)return -1;

k++;

x1=get_x(s[i]);

}

if(s[i]<='8'&&s[i]>='1')

{

if(k!=1)return -1;

y1=get_y(s[i]);

*x=x1; *y=y1; k=0;

if(chs[x1][y1]!=0)return -1;

chs[x1][y1]=p; j++;

if(j==n)break;

}

}

return 0;

}

//получить x

int get_x(char c)

{

return (int)(c-'a');

}

//получить y

int get_y(char c)

{

return (int)(c-'1');

}

//получить шахматную координату

char get_x1(int c)

{

return (char)('a'+c);

}

//получить шахматную координату

char get_y1(int c)

{

return (int)('1'+c);

}

//копирование текущего массива шагов

//в массив шагов для временного минимума

void cop(int n)

{

int i;

for(i=0; i

mx1[i]=mx[i]; my1[i]=my[i];

}

}

//вспомогательная функция для функции zamur

//проверка возможности шага для принцессы

void step(int x, int y, int p)

{

h=0;

switch(p)

{

case 1:

if(x+1<=7){

if(chs[x+1][y]!=1)h=1;

else{

if(x+2<=7&&chs[x+2][y]!=1)h=2;

}

}

break;

case 2:

if(x-1>-1){

if(chs[x-1][y]!=1)h=1;

else{

if(x-2>-1&&chs[x-2][y]!=1)h=2;

}

}

break;

case 3:

if(y+1<=7){

if(chs[x][y+1]!=1)h=1;

else{

if(y+2<=7&&chs[x][y+2]!=1)h=2;

}

}

break;

case 4:

if(y-1>-1){

if(chs[x][y-1]!=1)h=1;

else{

if(y-2>-1&&chs[x][y-2]!=1)h=2;

}

}

break;

}

}

//проверяем некоторые признаки -

//не замурована ли принцесса

int zamur()

{

int s, s1=0, s2=0, s3=0, s4=0;

int s11=0, s22=0, s33=0, s44=0;

int x1,y1, p1=0,p2=0,p3=0,p4=0,t=0;

step(xp,yp,1); s1=h; step(xp,yp,2); s2=h;

step(xp,yp,3); s3=h; step(xp,yp,4); s4=h;

s=s1+s2+s3+s4;

if(s==1){

chs[xp][yp]=1;

if(s1==1){

x1=xp+1;y1=yp;

}

if(s2==1){

x1=xp-1; y1=yp;

}

if(s3==1){

x1=xp; y1=yp+1;

}

if(s4==1){

x1=xp; y1=yp-1;

}

step(x1,y1,1); s1=h; step(x1,y1,2); s2=h;

step(x1,y1,3); s3=h; step(x1,y1,4); s4=h;

chs[xp][yp]=0;

if(s1+s2+s3+s4==0)s=0;

}

if(s==2){

if(s1==1){

chs[xp][yp]=1;

x1=xp+1;y1=yp;

step(x1,y1,1); s11=h; step(x1,y1,2); s22=h;

step(x1,y1,3); s33=h; step(x1,y1,4); s44=h;

if(s11+s22+s33+s44==0)p1=0;else p1=1;

chs[xp][yp]=0;

t=1;

}

if(s2==1){

chs[xp][yp]=1;

x1=xp-1;y1=yp;

step(x1,y1,1); s11=h; step(x1,y1,2); s22=h;

step(x1,y1,3); s33=h; step(x1,y1,4); s44=h;

if(s11+s22+s33+s44==0)p2=0;else p2=1;

chs[xp][yp]=0;

t=1;

}

if(s3==1){

chs[xp][yp]=1;

x1=xp;y1=yp+1;

step(x1,y1,1); s11=h; step(x1,y1,2); s22=h;

step(x1,y1,3); s33=h; step(x1,y1,4); s44=h;

if(s11+s22+s33+s44==0)p3=0;else p3=1;

chs[xp][yp]=0;

t=1;

}

if(s4==1){

chs[xp][yp]=1;

x1=xp;y1=yp-1;

step(x1,y1,1); s11=h; step(x1,y1,2); s22=h;

step(x1,y1,3); s33=h; step(x1,y1,4); s44=h;

if(s11+s22+s33+s44==0)p4=0;else p4=1;

chs[xp][yp]=0;

t=1;

}

if(t==1){

if(p1+p2+p3+p4==0)s=0;

}

}

return s; }


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət

    Ana səhifə