Vladislav_133 02 май 2010, 17:43
Внесу и я свою лепту в решение. Долго думал, как принцип минимизации (т.е. очередной шаг должен сокращать расстояние) применить в случае наличия препятствий. Придумал следующее. Пока нет препятствия, то действует принцип минимизации. Если при очередном шаге попадаешь на препятствие, то клетку с которой ты попадал на препятствие помечаем. Это значит, что прыжки с этой клетки не подвержены принципу минимизации. Надо еще по анализировать реальный выигрышь, но мне кажется он значительный. Вот программа на Си. Программа получилась длинноватой, но я доволен. Вот это действительно праздник!
- Код: Выделить всё
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <string.h>
#include <wchar.h>
#include <errno.h>
#include <sys/stat.h>
#include <malloc.h>
#include <unistd.h>
void step(int,int,int,int,int);
int n,pr,k,min,x2,y2,shn;
char * fi,* fi1, c;
int *a,*b, *a1,*b1;
char s[10];
int main()
{
int i,j,x1,y1,r1;
fscanf(stdin,"%d",&n);
if(n>0&&n<101)
{
fi=(char*)malloc(n*n);
a=(int*)malloc(sizeof(int)*n*n);
b=(int*)malloc(sizeof(int)*n*n);
a1=(int*)malloc(sizeof(int)*n*n);
b1=(int*)malloc(sizeof(int)*n*n);
fi1=(char*)malloc(n*n);
}else
{
fprintf(stdout,"Error!\n");
return 1;
}
//
i=0;
while(true)
{
fscanf(stdin,"%c",&c);
if(c<=32)continue;
*(fi+i)=c; *(fi1+i)='-';
a[i]=0; b[i]=0; a1[i]=0; b1[i]=0;
if(c=='A')
{
x1=i%n; y1=i/n;
}
if(c=='B')
{
x2=i%n; y2=i/n;
}
i++;
if(i==n*n)break;
}
//
pr=0;
min=n*n;
shn=abs(x1-x2)+abs(y1-y2);
r1=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
k=0; if(x1<n-1)step(x1,1,y1,0,r1);
k=0; if(y1<n-1)step(x1,0,y1,1,r1);
k=0; if(x1>0)step(x1,-1,y1,0,r1);
k=0; if(y1>0)step(x1,0,y1,-1,r1);
if(pr==1)
{
fprintf(stdout,"%d\n",min);
for(i=0; i<min; i++) fprintf(stdout,"%d %d;",a1[i],b1[i]);
fprintf(stdout,"\n");
}
else
{
fprintf(stdout,"No pass\n");
}
free(fi);free(a); free(b);free(fi1);
return 0;
}
//
void step(int x,int dx,int y,int dy,int r)
{
int xx,yy,rr,i;
xx=x+dx; yy=y+dy;
if(*(fi+xx+yy*n)=='q'||min==shn||k+1>min)
{
return;
}
a[k]=xx; b[k]=yy;
if(*(fi+xx+yy*n)=='#')
{
*(fi1+x+y*n)='+';
return;
};
if(*(fi+xx-1+yy*n)=='#'||*(fi+xx+1+yy*n)=='#'||*(fi+xx+(yy+1)*n)=='#'||*(fi+xx+(yy-1)*n)=='#')
{
*(fi1+xx+yy*n)='+';
}
k++;
if((*(fi+xx+yy*n)=='B'))
{
pr=1;
if(min>k)
{
min=k;
for(i=0; i<k; i++)
{
a1[i]=a[i]; b1[i]=b[i];
}
}
k--;
return;
};
rr=(xx-x2)*(xx-x2)+(yy-y2)*(yy-y2);
if(rr<r||*(fi1+x+y*n)=='+')
{
*(fi+xx+yy*n)='q';
if(xx<n-1)step(xx,1,yy,0,rr);
if(yy<n-1)step(xx,0,yy,1,rr);
if(xx>0)step(xx,-1,yy,0,rr);
if(yy>0)step(xx,0,yy,-1,rr);
*(fi+xx+yy*n)='.';
}
k--;
}
//
Исправлено
Последний раз редактировалось
Vladislav_133 03 май 2010, 11:10, всего редактировалось 3 раз(а).