OJ Board

Posted: **Fri Sep 05, 2003 3:38 pm**

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]

Posted: **Sat Jan 21, 2006 5:47 pm**

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);
	}
}

Posted: **Sat Jan 21, 2006 8:03 pm**

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]

Posted: **Wed Feb 22, 2006 9:25 pm**

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

Posted: **Mon Mar 06, 2006 9:54 pm**

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.

Posted: **Sat Mar 18, 2006 12:09 pm**

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

OJ Board

393 - The Doors

393 - Wrong Answer, I can't belive it. plzzzzzzzzzz help

393 - The Doors

I've changed my code but i'm getting WA...