Page 2 of 2

### 10610 - Gopher & Hawks

Posted: Tue Mar 30, 2004 11:34 pm
I use the following procedure:

1. mark all (u,v) such that gopher can go from u to v in m minutes with its speed v m/sec.

2.Then call bfs.

But get wrong ans. Is the procedure wrong?

Posted: Wed Mar 31, 2004 6:11 am
Yes, this is the correct procedure.
perhaps your program does not work for special cases or you are making spelling mistakes.

Posted: Thu May 06, 2004 3:40 pm
Why does this get WA, I'm going sligtly mad ...

[pascal]

program miazio;

const
max = 10000;

{}

function odl (ax, ay, bx, by:real):real;
begin

odl:=sqrt (sqr (ax - bx) + sqr (ay - by));

end;

{}

type mia = record
x, y:real;
end;

var
t:array [1..max] of mia;
kro:array [1..max] of longint;
kolej:array [1..max] of longint;
v, mp, pysk, ogon:longint;
d, i, j, k, l:longint;
m:real;
nmwk1, nmwk2, rea:boolean;

{}

begin

repeat

if (v = 0) and (mp = 0) then exit;

m:=v * 60 * mp;
i:=0;

while not eoln do
begin

inc (i);
if eoln then break;

end;

j:=i;
kolej :=1;
ogon:=0;
pysk:=1;
rea:=false;

for i:=1 to max do
kro :=10000;

while (ogon <> pysk) and (rea = false) do
begin

inc (ogon);

for i:=2 to j do
if (i <> kolej [ogon]) and (odl (t [kolej [ogon]].x, t [kolej [ogon]].y, t .x, t .y) < m) then
if kro = 0 then

begin

inc (pysk);
if i = 2 then rea:=true;
kolej [pysk]:=i;
if i <> 1 then
if (kro > kro [kolej [ogon]] + 1) then
kro :=kro [kolej [ogon]] + 1;

end;

end;

if rea then writeln ('Yes, visiting ', kro  - 1, ' other holes.') else
writeln ('No.');

until eof;

end.

[/pascal]

Any ideas? Plz help Posted: Tue Jun 29, 2004 11:53 pm
I use the following procedure

1.- it creates the graph
2.- use algorithms Dijkstra or Lee,

[c]

int lee(int des){
short int r = -1, i, j, in = 0, fin = 0 , x;
d[fin] = 0; cola[fin++] = 0;
v = 1;
while(in < fin && r < 0){
x = cola[in];
for(i=0;i<ng[x];i++)
if(!v[g[x]]){
j = g[x];
if(j == des){ r = d[in]+1; break;}
cola[fin] = j;
d[fin] = d[in]+1;
v[j] = 1;
fin++;
}
in++;
}
return r;
}

main(){
---
/*0 is initial hole
1 is teminal hole
*/
holes = lee(1);
if(holes < 0) printf("No.\n");
else printf("Yes, visiting %d other holes.\n", holes-1);
---
}
[/c]

and AC Posted: Sat Jul 03, 2004 7:37 pm
I use BFS and get WA very many times.I can't find my error.May be there are some spacial cases ,please,give me some test cases.
This is my code.
[pascal]var x,y:array[0..1100] of real;
s:array[0..1100] of longint;
i,j,k,n,v,m:longint;
xs,ys,rr:real;
procedure solve;
var i,j,k:longint;
f:boolean;
begin
for i:=1 to n do
s:=0;
k:=1;
s:=1;
repeat
f:=true;
for i:=1 to n do
if s=k then
for j:=1 to n do
if i<>j then
begin
rr:=sqrt(sqr(x-x[j])+sqr(y-y[j]));
if (rr<=m*60*v) and (s[j]=0) then
begin
s[j]:=k+1;
f:=false;
end;
end;
k:=k+1;
until (f=true) or (s[n]<>0);
end;
begin
repeat
for i:=1 to 1000 do
begin
x:=0;y:=0;s:=0;
end;
if (v=0) and (m=0) then break;
j:=0;
i:=1;
while not eoln do
begin
i:=i+1;
if eoln then break;
end;
n:=i+1;
x[n]:=xs;
y[n]:=ys;
solve;
if s[n]=0 then writeln('No.') else
writeln('Yes, visiting ',s[n]-2,' other holes.');
until (m=0) and (v=0);
end.
[/pascal]

Posted: Sun Jul 04, 2004 12:11 pm
I can't find my mistake.
I can't understand why I'm getting WA.
I get WA with BFS;TLE with FLoyd and WA with Deikstra. May be i'm doing something wrong when read the coordinates.Please help me. Thanks.

Posted: Sun Jul 04, 2004 6:43 pm
Finaly i find my mistake and got AC. I was making mistake while reading. I got AC with BFS.But WA with Diejkstra. ### So what was your mistake?

Posted: Mon Jul 19, 2004 5:49 pm
I have also WA. Probably it will help me.

Posted: Mon Jul 19, 2004 7:30 pm
If you are writing by pascal then i can tell you my mistake.I make mistake when read the coordinats. You must do it like this.
[pascal]
i:=0;
while not eoln do
begin
i:=i+1;
end;
[/pascal]

Posted: Fri Aug 13, 2004 11:01 am
Hello Kiha... !!

I have just got Ac with this task....
Don't use strings... (i.e. procedure lam) use simply reals.

< Nie wczytuj stringow tylko od razu wczytuj dwa reale... tak ja robilem i dostalem AC... >

### 10610 - WA! Why Dejkstra does not work???

Posted: Wed Sep 01, 2004 11:46 pm
Could smb help me?
Why Dejkstra does not work???
Give me some tests!

program p10610;
const
MAX = 1002;
var
g:array[0..MAX+1,0..MAX+1] of double;
d,x,y:array[0..MAX+1] of double;
Holes,w,v,m,i,j:integer;
min,di,DIST:double;
s:array[0..MAX+1] of boolean;
pi:array[0..MAX+1] of integer;

function minimum(i,j:double):double;
begin
if i<j then minimum := i
else minimum := j;
end;

begin
while True do
begin
if v + m = 0 then break;
DIST := v * m * 60; {max distance to run not to be eaten}
Holes := 1;
while not eoln do
begin
Inc(Holes);
end;
for i:=0 to Holes do for j:=0 to Holes do
if i=j then g[i,j] := 0 else g[i,j] := MAXLONGINT;
for i:=0 to Holes do
for j:=0 to Holes do
if i <> j then
begin
di := sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
if di <= DIST then begin g[i,j] := di; g[j,i] := di; end;
end;

for i:=0 to Holes do d[i] := g[0,i];
FillChar(s,sizeof(s),0);
d := 0; s := True;
FillChar(pi,sizeof(pi),0);
for j := 1 to Holes do
begin
min := MAXLONGINT;
for i:= 0 to Holes do
if ((not s[i]) and (d[i] < min)) then
begin
min := d[i]; w := i;
end;
for i:=0 to Holes do
if (not s[i]) then
if d[w] + g[w,i] < d[i] then
begin
d[i] := d[w] + g[w,i]; pi[i] := w;
end;
s[w] := True;
end;

if d < MAXLONGINT then
begin
i := 1; j := 0;
while pi[i] <> 0 do
begin
i := pi[i]; Inc(j);
end;
writeln('Yes, visiting ',j,' other holes.');
end else writeln('No.');
end;
end.

Posted: Sun Jul 15, 2007 9:57 pm
I have used DFS approach with DP . I have absolute no idea why I am getting TLE . Is there anything wrong in my input taking or the algo is too slow?? I found in this forum that people used BFS to have solved this problem.So, using DFS would not be algorithmically slower.

here is my code ..

Code: Select all

``````#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>

#define INF 99999

using namespace std;

class point
{
public:
double x,y;
};

point P;
char s;
int count;//number of points
double con;//condition to be satisfied
bool used;//used marker
int d;//memo

double dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int search(int p,bool used[])
{
if(p==1)
{
d[p]=1;
return 1;
}
if(d[p]<INF)
{
return d[p];
}
register int min=INF,i,x;
for(i=0;i<count;i++)
{
if(!used[i] && dis(P[p],P[i])<=con)
{
used[i]=true;
x=1+search(i,used);
if(x<min)
{
min=x;
}
used[i]=false;
}
}
d[p]=min;
return min;
}
int main(void)
{
register double v,t;
register char dummy;
while(1)
{
scanf("%lf%lf",&v,&t);
if(v==0 && t==0)
{
break;
}
else
{
con=v*t*60.0;
}
gets(dummy);
count=0;
while(1)
{
gets(s);
if(strcmp(s,"")==0)
{
break;
}
sscanf(s,"%lf%lf",&P[count].x,&P[count].y);
d[count]=INF;
used[count]=false;
count++;
}

used=true;
register int x=search(0,used);
if(x<INF)
{
printf("Yes, visiting %d other holes.\n",x-2);
}
else
{
printf("no.\n");
}
}
return 0;
}
``````

### Re: 10610 - Gopher and Hawks

Posted: Fri Feb 13, 2009 4:15 pm
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<queue>

using namespace std;
struct point
{
double x,y;
};
int main()
{
double speed, tim;
cin>>speed>>tim;
while(speed!=0 && tim!=0)
{
tim*=60.0000000;
vector<point>v;
double maxi=tim*speed;
maxi*=maxi;
point start,target;
cin>>start.x>>start.y>>target.x>>target.y;
v.push_back(start);
v.push_back(target);
double x,y;
string str;
getline(cin,str);
while(true)
{
getline(cin,str);
if(str.size()==0) break;
stringstream ss(str);
ss>>x>>y;
point p1; p1.x=x; p1.y=y;
v.push_back(p1);
}

int len=v.size();
bool mat[len][len];
memset(mat,false,sizeof(len));
int mem[len];
memset(mem,0,sizeof(mem));

for(int i=0;i<len;i++)
{
for(int j=i+1;j<len;j++)
{
double dist=pow((v.x-v[j].x),2.0) + pow((v.y-v[j].y),2.0);
if(maxi-dist>=0.00000)
{
mat[j]=true;
mat[j]=true;
}
}
}

/* for(int i=0;i<len;i++)
{
for(int j=0;j<len;j++)
{
cout<<mat[j]<<" ";
}
cout<<endl;
}*/

queue<int>Q;
Q.push(0);

int ret=-1;

while(!Q.empty())
{
int temp=Q.front();
Q.pop();
if(temp==1){ ret=temp; break;}

for(int i=0;i<len;i++)
{
if(mat[temp]==true && mem==0)
{
Q.push(i);
mem=mem[temp]+1;
}
}
}

if(ret==-1) cout<<"No.\n";
else
{
cout<<"Yes, visiting "<<mem[ret]-1<<" other holes.\n";

}
cin>>speed>>tim;

v.clear();
}
system("pause");
}

could sm1 xplain to me whats the problem in this code
here is the algo that i have used......

1)made a bool matrix based on the distance between the two points i.e if the point is close then 1 otherwise 0
2) used the bfs to move from the start to target point. if the queue is emptied b4 reaching then we have not found the target so ans is "No" otherwise i have stored the number of steps which has been used to reach to that point...

ny suggestion regarding the query will be xtremely helpful!!!

### 10610 - Gopher and Hawks

Posted: Mon Nov 28, 2011 4:57 pm
BFS problem

This is just a BFS problem with a bit of math.
1. Find all adjacency using this condition, consider two holes connected if the distance between them is less than or equal to v*m*60.
2. Run BFS on the gopher holes to destination hole.
3. If gopher reach to destination hole then print length of shortest path -1.
4. Otherwise print No.

try this

Code: Select all

``The input/output is incorrect so it has been removed.``
Accepted ... 