## 393 - The Doors

Moderator: Board moderators

davor
New poster
Posts: 8
Joined: Sat Jun 28, 2003 11:04 pm

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

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
while n>=0 do begin
for i:=1 to n do begin
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;
end;
end.
[/pascal]

yolongyi
New poster
Posts: 5
Joined: Mon Jan 16, 2006 9:19 pm
Location: Korea

### 393 - The Doors

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);
}
}``````
hi... I am a student stydying Computer Programming. Plz give me your hand.. I'll give U too if I can..

yolongyi
New poster
Posts: 5
Joined: Mon Jan 16, 2006 9:19 pm
Location: Korea

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

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]
hi... I am a student stydying Computer Programming. Plz give me your hand.. I'll give U too if I can..

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
Why would you use backtracking when something like dijkstra would work?

Tritri
New poster
Posts: 5
Joined: Mon Mar 06, 2006 2:04 am
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
New poster
Posts: 5
Joined: Mon Mar 06, 2006 2:04 am
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
``````