НОИ 2005 - 2 кръг, Задача A3.
ПЪТЕКА
Условието на задачата може да прочетете
тук.
Решение
Решението на задачата се базира на един метод,
който може да бъде наречен компресиране (свиване) на равнината. За
целта старите координати на правоъгълниците се заменят с нови по
следния начин:
1.
Първо се проверява какви различни Х и
съответно Y координати се срещат в
картинката. Те са най-много 2*K+2 на
брой.
2.
Тези координати се сортират и на всяко число се съпоставя друго
(новите координати),
което съответства на индекса в масива.
Пример:
Ако
имаме следните различни Х координати: 0 3 7 33 44 60 78 100, то на тях се
съпоставят съответно на 0 - 0, на 3 - 1, на 7 - 2, на 33 - 3, на 44 - 4, на 60
- 5, на 78 -6, на 100 - 7.
3. За
всеки правоъгълник изчисляваме новите му координати.
Пример:
ако
имаме и следните Y
координати 0 4 16 27 36 49 100, тогава
на правоъгълник (3,16)-(78,36) новите
координати са (1,2)-(6,4).
След като вече имаме новите им координати можем
да направим следното нещо. Построяваме правоъгълна таблица с размери
(броя на различните Х координати-1) и
(броя на различните Y координати-1).След това за всеки правоъгълник
запълваме
този участък от таблицата, който съответства на новите му
координати. Пример:
имаме координатите споменати по
горе и
следните правоъгълници:
(3,16)-(78,36) , (60,49)-(78,100) ,
(3,4)-(7,16) , (33,0)-(44,4) , (60,4)-(78,16)
тогава таблицата би изглеждала по следния
начин:
100
0 0 0 0 0 2 0
49
0 0 0 0 0 2 0
36
0 1 1 1 1 1 0
27
0 1 1 1 1 1 0
16
0 3 0 0 0 5 0
4
0 0 0 4 0 0 0
0
0 3 7 33 44 60 78 100
Сега получихме таблица в която има запълнени
клетки и празни клетки. Ние можем да се движим само по празните
клетки. Ако крайната клетка (в горния десен ъгъл) е запълнена
задачата няма решение, както и ако началната клетка в долния ляв
ъгъл е запълнена. Ако не са то можем от точка (0,0) да прокараме отсечка до средата на
клетката в долния ляв ъгъл, както и от крайната точка до горната
дясна клетка. сега остава да свържем тези 2 точки отново с отсечки.
Ще използвам само отсечки успоредни на координатните оси. Сега
трябва на намерим път между двете крайни клетки. Това е стандартна
задача за търсене на път в граф и може да се реши по много начини.
Аз ползвам BFS, тъй като то ще намери
минимален път (не по отночение на завоите, които нас ни интересуват,
но все пак минималният път който ще намери ще спази ограничението).
В случая има единствен път:
0 0
-> 1 0 -> 2 0 -> 2 1 -> 3 1 -> 4 1 -> 4 0 -> 5
0 -> 6 0 -> 6 1 -> 6 2 -> 6 3 -> 6 4 -> 6
5
Но
тъй като можем да си правим колкото си искаме дълги отсечки, то ако
имаме две съседни в една посока можем да ги съединим:
0 0
-> 2 0 -> 2 1 -> 4 1 -> 4 0 -> 6 0 -> 6 1 -> 6
5
Сега свързваме последоватено центровете на тези
клетки (аз за център приемам центъра на правоъгълника който е
заключен между старите координати, които съответстват на краищата на
клетката). Така в този случай би се получил следният
път:
0
0(това е началото, а не средата на клетка 0 0) -> 1.5 2 -> 20
2 -> 20 10 -> 52 10 -> 52 2 -> 89 2 -> 89 74.5 ->
100 100
Строго доказателство, че винаги намереният път
ще е с по малко от 4K
отсечки не мога да дам, но на тестовете на журито беше много
по-малко от K.
Примерна
реализация:
#include<stdio.h>
#include<stdlib.h>
#define in stdin;//fopen("c:\\tp\\tests\\path.in","r")
#define mx 512
FILE*fn;
typedef struct {int x,y;}pos;
int x1[mx],x2[mx],y1[mx],y2[mx];
int ss[mx*2][mx*2];
int v[mx*2][mx*2];
pos p[mx*2][mx*2];
int mov[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int x[mx*2],y[mx*2];
int q1,q2,q3,c1,c2,c3,c4,c5,c,n,m,cy,cx;
int cmp(const void*a,const void*b)
{return *((int*)a)-*((int*)b);}
pos q[mx*10];
int qin,qou;
pos e1,e2;
pos ans[mx*22];
int ac;
int test(pos e1,int m,pos*e2)
{pos e3;
e3.x=mov[m][0]+e1.x;
e3.y=mov[m][1]+e1.y;
if(e3.x<0||e3.y<0||e3.x>=cx-1||e3.y>=cy-1)return 0;
if(ss[e3.x][e3.y]==1)return 0;
*e2=e3;
return 1;}
int main()
{fn=in;
fscanf(fn,"%d %d %d",&n,&m,&c);
if(c==0)
{printf("0\n");
return 0;}
for(q1=0;q1<c;q1++)fscanf(fn,"%d %d %d %d",x1+q1,y1+q1,x2+q1,y2+q1);
fclose(fn);
for(q1=0;q1<c;q1++)x[cx++]=x1[q1];
for(q1=0;q1<c;q1++)x[cx++]=x2[q1];
for(q1=0;q1<c;q1++)y[cy++]=y1[q1];
for(q1=0;q1<c;q1++)y[cy++]=y2[q1];
x[cx++]=0;
x[cx++]=n;
y[cy++]=0;
y[cy++]=m;
qsort(y,cy,sizeof(y[0]),cmp);
qsort(x,cx,sizeof(x[0]),cmp);
c1=cx;
cx=1;
for(q1=1;q1<c1;q1++)if(x[q1]!=x[q1-1])x[cx++]=x[q1];
c1=cy;
cy=1;
for(q1=1;q1<c1;q1++)if(y[q1]!=y[q1-1])y[cy++]=y[q1];
for(q1=0;q1<c;q1++)
{for(q2=0;q2<cx;q2++)if(x1[q1]==x[q2])break;c1=q2;
for(q2=0;q2<cx;q2++)if(x2[q1]==x[q2])break;c2=q2;
for(q2=0;q2<cx;q2++)if(y1[q1]==y[q2])break;c3=q2;
for(q2=0;q2<cx;q2++)if(y2[q1]==y[q2])break;c4=q2;
for(q2=c1;q2<c2;q2++)for(q3=c3;q3<c4;q3++)
ss[q2][q3]=1;}
if(ss[0][0]==1)
{printf("-1\n");
return 0;}
e1.x=e1.y=0;
q[qin++]=e1;
v[e1.x][e1.y]=1;
while(qin!=qou)
{e1=q[qou++];
for(q1=0;q1<4;q1++)if(test(e1,q1,&e2))
if(!v[e2.x][e2.y])
{v[e2.x][e2.y]=1;
p[e2.x][e2.y]=e1;
q[qin++]=e2;}}
if(!v[cx-2][cy-2])
{printf("-1\n");
return 0;}
e1.x=cx-2;
e1.y=cy-2;
ans[ac++]=e1;
while(e1.x+e1.y!=0)
{e1=p[e1.x][e1.y];
ans[ac++]=e1;
if(ac>2)
if((ans[ac-1].x==ans[ac-2].x&&ans[ac-1].x==ans[ac-3].x)||
(ans[ac-1].y==ans[ac-2].y&&ans[ac-1].y==ans[ac-3].y))
{ans[ac-2]=ans[ac-1];
ac--;}
}
printf("%d\n",ac);
for(q1=ac-1;q1>=0;q1--)
printf("%.2lf %.2lf\n",
(x[ans[q1].x]*1.0+x[ans[q1].x+1]*1.0)/2.0,
(y[ans[q1].y]*1.0+y[ans[q1].y+1]*1.0)/2.0);
return 0;}
Автор: Светослав Колев
обратно към брой 27
|