393 - The Doors

[davor]

The problem is simple but I can't find out why WRONG ANSWER
[pascal]var i,j,k,l,o,n,m:integer;
x1,x2,y1,y2,y3,a1,b1,dis:real;
a:array[0..19,1..5] of real;
b:array[0..19,1..4] of real;

function dist(x1,y1,x2,y2:real):real;
begin
dist:=sqrt(sqr(x1-x2)+sqr(y2-y1));
end;

begin
read(n);
while n>=0 do begin
for i:=1 to n do begin
read(a[i,1],a[i,2],a[i,3],a[i,4],a[i,5]);
b[i,1]:=100000; b[i,2]:=100000; b[i,3]:=100000; b[i,4]:=100000;
end;
a[0,1]:=0; a[0,2]:=5; a[0,3]:=5; a[0,4]:=10; a[0,5]:=10;
b[0,1]:=0; b[0,2]:=0; b[0,3]:=100000; b[0,4]:=100000;
a[n+1,1]:=10; a[n+1,2]:=5; a[n+1,3]:=5; a[n+1,4]:=10; a[n+1,5]:=10;
b[n+1,1]:=100000; b[n+1,2]:=100000; b[n+1,3]:=100000; b[n+1,4]:=100000;
for i:=1 to n+1 do begin
for o:=1 to 4 do begin
for j:=0 to i-1 do begin
for k:=1 to 4 do begin
m:=0;
x1:=a[j,1]; y1:=a[j,k+1];
x2:=a[i,1]; y2:=a[i,o+1];
a1:=(y2-y1)/(x2-y1);
b1:=y1-a1*x1;
for l:=j+1 to i-1 do begin
y3:=a[l,1]*a1+b1;
if (y3<a[l,2]) or ((y3>a[l,3]) and (y3<a[l,4])) or (y3>a[l,5]) then m:=1;
end;
dis:=dist(a[j,1],a[j,k+1],a[i,1],a[i,o+1])+b[j,k];
if (m=0) and (dis<b[i,o]) then b[i,o]:=dis;
end;
end;
if (i=n+1) and (o=1) then writeln(b[i,o]:0:2);
end;
end;
read(n);
end;
end.
[/pascal]

[yolongyi]

My code is getting WA....why??
plz help me...
tell me what is wrong...
or can anyone give me some test case??

Code: Select all

#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;

int vertices, walls;
float W[82][82], X[20], Y[20][4];
float minimum, sum;

bool able(int w1,int v1,int w2,int v2){
	int w;
	float dx,dy, y;
	if(w1-w2==1) return true;
	else{
		dx=X[w1]-X[w2];
		dy=Y[w1][v1]-Y[w2][v2];
		if(w1==0&&v1!=0) return false;
		else if(w2==walls+1&&v2!=0) return false;
		for(w=w1+1;w<w2;w++){
			y = (dy/dx)*X[w] + (Y[w1][v1]-(dy/dx)*X[w1]);
			if(!((Y[w][0]<=y&&y<=Y[w][1]) || (Y[w][2]<=y&&y<=Y[w][3]))) return false;
		}
	}
	return true;
}

int pos(int w,int v){
	if(w==0) return 0;
	else if(w==walls+1) return vertices-1;
	else return (w-1)*4+v+1;
}

void go(int v){
	int i;
	if(sum<minimum){
		if(v==vertices-1) minimum=sum;
		else{
			for(i=v+1;i<vertices;i++){
				if(v==0) sum=0.00;
				if(W[v][i]!=99999.0){
					sum+=W[v][i];
					go(i);
				}
			}
		}
	}
}

void main(){
	int i, j, k, t;
	while(true){
		cin>>walls;
		if(walls==-1) break;
		vertices = walls*4+2;
		X[0]=0.0;X[walls+1]=10.0;
		Y[0][0]=Y[walls+1][0]=5.0;
		for(i=1;i<=walls;i++){
			cin>>X[i];
			for(j=0;j<4;j++) cin>>Y[i][j];
		}
		for(i=0;i<vertices;i++)	for(j=0;j<vertices;j++) W[i][j]=99999.0;
		for(i=0;i<=walls;i++){
			for(j=0;j<4;j++){
				for(k=i+1;k<=walls+1;k++){
					for(t=0;t<4;t++){
						if(able(i,j,k,t)) W[pos(i,j)][pos(k,t)]=sqrt(pow(X[i]-X[k],2)+pow(Y[i][j]-Y[k][t],2));
					}
				}
			}
		}
		sum=0.00;
		minimum=999999.0;
		go(0);
		printf("%.2f\n",minimum);
	}
}

[yolongyi]

My previous code does not test all case
so i've changed my code..
but i'm getting WA...
why..
here is my code that changed...
is that bidirectional way??
i dont take care...that

Code: Select all

#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;

int vertices, walls;
float W[100][100], X[30], Y[30][4];
float minimum, sum;

bool able(int w1,int v1,int w2,int v2){
	int w;
	float dx,dy, y;
	if(w1-w2==1) return true;
	else{
		dx=X[w1]-X[w2];
		dy=Y[w1][v1]-Y[w2][v2];
		if(w1==0&&v1!=0) return false;
		else if(w2==walls+1&&v2!=0) return false;
		for(w=w1+1;w<w2;w++){
			y = (dy/dx)*X[w] + (Y[w1][v1]-(dy/dx)*X[w1]);
			if(!((Y[w][0]<=y&&y<=Y[w][1]) || (Y[w][2]<=y&&y<=Y[w][3]))) return false;
		}
	}
	return true;
}

int pos(int w,int v){
	if(w==0) return 0;
	else if(w==walls+1) return vertices-1;
	else return (w-1)*4+v+1;
}

void go(int v){
	int i, j;
	if(sum + sqrt(pow(X[(v+3)/4]-10,2)+pow(Y[(v+3)/4][(v-1)%4]-5,2)) < minimum){
		if(v==vertices-1) minimum=sum;
		else{
			if(v==0) j=1;
			else j=v+4-(v-1)%4;
			for(i=v+1;i<vertices;i++){
				if(W[v][i]!=99999.0){
					sum+=W[v][i];
					go(i);
					sum-=W[v][i];
				}
			}
		}
	}
}

void main(){
	int i, j, k, t;
	while(true){
		cin>>walls;
		if(walls==-1) break;
		vertices = walls*4+2;
		X[0]=0.0;X[walls+1]=10.0;
		Y[0][0]=Y[walls+1][0]=5.0;
		for(i=1;i<=walls;i++){
			cin>>X[i];
			for(j=0;j<4;j++) cin>>Y[i][j];
		}
		for(i=0;i<vertices;i++)	for(j=0;j<vertices;j++) W[i][j]=99999.0;
		for(i=0;i<=walls;i++){
			for(j=0;j<4;j++){
				for(k=i+1;k<=walls+1;k++){
					for(t=0;t<4;t++){
						if(able(i,j,k,t)) W[pos(i,j)][pos(k,t)]=sqrt(pow(X[i]-X[k],2)+pow(Y[i][j]-Y[k][t],2));
					}
				}
			}
		}
		sum=0.00;
		minimum=999999.0;
		go(0);
		printf("%.2f\n",minimum);
	}
}

[/b]

[sclo]

Why would you use backtracking when something like dijkstra would work?

[Tritri]

Hi, I'm think your code forces the path to past just over the vertex and if you see the example you will see that the solution can 'pass' across the door without 'touch' it.

[Tritri]

I try to solve this problem but the response was allways WA too... and this problem is very difficult to test and debug. Can someone who has solved this prob. try to pass this test and say the correct result??

Code: Select all

18
1 3 3.5 8.5 9
1.5 1 3 4 5
1.7 0.5 0.6 0.7 1
2 8.4 8.5 9.5 9.6
2.1 1 2 3 4
3 3 3.5 8.5 9
3.5 1 3 4 5
3.7 0.5 0.6 0.7 1
4 8.4 8.5 9.5 9.6
6.1 1 2 3 4
6.2 5 5.5 6.1 6.2
6.4 1 1.5 2 2.4
7 4 5 6 7
7.5 1 1.2 1.3 1.4
7.6 2 2.1 2.2 2.3
7.7 6 6.1 7 7.5
8 2 3 4 5
8.5 1 2 9.5 10
-1