## 10977 - Enchanted Forest

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
This is what my program does (Impossible.):

Code: Select all

``````0000100000
0010010000
0101111100
1001111100
0011111110
1001111100
1111111100
1111010001
1111000100
1111101110
``````
Mind you, it keeps timing out, but I'm convinced it works.

You are, basically, drawing a circle around a point with the radius L. so, if L is 3, the spot 2 left and 2 down from the given spot should be inside it (because 2*2+2*2 <= 3*3).

Hope that helps.

Darko
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Well actually the case is not valid, since loudness >= 1 (Read the problem description again...)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Well, just remove that Jigglypuff then! :)
(other than that my grid should work, right?)

I liked the whole set (although I got only 2 at the contest time), but I can't figure out why my BFS is too slow on OJ.

Did you guys make Java solutions? I know it's just an online contest, and we are supposed to learn from it (and I did!), but I think for the real thing, problem setters are supposed to provide the solutions in all languages accepted.

Darko
tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Thanks, Darko and Observer.
Finally, I could get Accepted

My WA code was failed because I've ignored about 'Euclidean distance'.
I vaguely understood this until now.
I am glad to obtain this knowledge.

Best regards.
Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
I agree with Larry. I think 200*200 should be good enough size for the queue. No of enque in one step should be much less than that. No of total enque should always be less than 200*200.

I dont seem to understand the code of shihab that well .. but if you are enqueing the same cell more than once, no matter what size of queue u use, u can at best get TLE, if not RTE.
Where's the "Any" key?
shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

### Still getting RTE

Its true that my code is a bit clumsy, sorry 4 that. Inside main() i've mostly worked for taking the input and constructing the forest grid(adMat[][]). And no point is enqued more than once, since the entry colour[j] is maintained to check wheather a point adMat[j] was previously visited or not. So,i don't think this would cause a TLE. And still cannot find the reason 4 RTE. Plz hlp.

Shihab
Shihab
CSE,BUET
Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
Your code is not clumsy, it just did not match my own spacing tradition

anyway, I went through your code. One reason for getting RTE can be

Your change1[2][4] array is traversed for k = 0 to 7

Where in your code do you consider the euclid distance between two cells ???

While considering the circle covered by JigglePuff it is not necessary that the covered cell will be in one of the eight directions from the center e.g. Let the center is (1,1) and we have loudness L=5, then the cell (2,3) will be dangerous.
Where's the "Any" key?
mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
Why don't you do what I've suggested? If I'm not very much mistaken then you should get of RTE (don't know about WA though, that's something else).
StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

### 10977 - Enchanted Forest

Hello. I need some help.

This is sample input.
5 5
5
1 2
1 3
1 4
1 5
2 5
1
4 3 1
S - Start
F - Finish
# - border and blacked areas
X - Jigglypuff.
#######
#S#####
#_____##
#______#
#__X___#
#______F#
#######
Did I understand right this sample?
Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Code: Select all

``````#######
#S#####
#____##
#__#__#
#_#X#_#
#__#_F#
#######
``````
You must take into account Jigglypuff and its loudness.
Its loudness is circular.
StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
Emilio, Did I understand right that Euclidean distance is a distance between centers of places?
StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
Emilio, thanks for you explanation. I got Acc.
shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:
I've changed my code now & has got rid of RTE. But now I'm getting WA. I just don't get it. Can anyone hlp. I've considered curtesian distance between cells while editing the map 4 jiggypuffs.

Code: Select all

``````#include<cstdio>
#include<queue>
#include<cmath>

using namespace std;

#define INF 9999999

typedef struct Point{
int r,c;
} Point;

queue<Point> Q;
int row,col;
int map[205][205];
int d[205][205];
int visited[205][205];
int change[2][4];

void i_change(){
change[0][0]=-1;
change[1][0]=0;
change[0][1]=1;
change[1][1]=0;
change[0][2]=0;
change[1][2]=-1;
change[0][3]=0;
change[1][3]=1;
}
void init();
void BFS();

void main(){
int i,j,k,m,p,q,r,nr,nc;
i_change();

while(scanf("%d %d",&row,&col)==2){
if(!row && !col) break;
init();

//taking input of the obstacles and editing the map as necessary
scanf("%d",&m);

for(i=0;i<m;i++){
scanf("%d %d",&j,&k);
map[j][k]=0;
}

scanf("%d",&m);

//taking input 4 jiggypuffs and editing the map as necessary.
//considered curtesian distance
for(i=0;i<m;i++){
scanf("%d %d %d",&p,&q,&r);

nr=p-r;
nc=q-r;

for(j=nr;j<=p+r;j++){
for(k=nc;k<=q+r;k++){
if(j>=1 && j<=row && k>=1 && k<=col){
if(sqrt((j-p)*(j-p) + (k-q)*(k-q)) <=(double)r) map[j][k]=0;
}
}
}
}

if(map[1][1]) BFS();

if(d[row][col]!=INF) printf("%d\n",d[row][col]);
else printf("Impossible.\n");
}
}

void init(){
int i,j;

for(i=1;i<=row;i++){
for(j=1;j<=col;j++){
map[i][j]=1;
visited[i][j]=0;
d[i][j]=INF;
}
}

d[1][1]=0;
visited[1][1]=1;
}

void BFS(){
int j,nr=0,nc=0;
Point p;
p.r=p.c=1;
while(!Q.empty()) Q.pop();

Q.push(p);

while(!Q.empty()){
p=Q.front();
Q.pop();

for(j=0;j<4;j++){
nr=change[0][j]+p.r;
nc=change[1][j]+p.c;

if(nr>=1 && nr<=row && nc>=1 && nc<=col && map[nr][nc]==1 && !visited[nr][nc]){
visited[nr][nc]=1;
d[nr][nc]=d[p.r][p.c]+1;
p.r=nr;
p.c=nc;
Q.push(p);
}
}
}
}

Plz somebody hlp(Sugg,I/Os anything...).

-Shihab

``````
Shihab
CSE,BUET
tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Hi, shihabrc.
I think the main source of your WA is the part of BFS or decision, simply.
And small condition (ex. when the start point and goal point are same) should be added.

Try the following input set.

Code: Select all

``````1 1
0
0
1 1
1
1 1
0
1 1
0
1
1 1 0
10 10
0
1
3 5 3
5 5
5
1 2
1 3
1 4
1 5
2 5
1
4 3 1
5 5
6
1 2
1 3
1 4
1 5
2 5
3 5
1
4 3 1
6 7
3
4 5
5 4
6 6
2
2 6 1
3 2 1
5 5
5
1 1
1 3
1 4
1 5
2 5
1
4 3 1
5 5
5
5 5
1 3
1 4
1 5
2 5
1
4 3 1
10 10
4
1 5
2 3
4 1
8 10
4
3 2 0
5 6 3
10 1 4
10 8 1
15 15
0
1
7 7 6
0 0
``````
Output is :

Code: Select all

``````0
Impossible.
Impossible.
18
8
Impossible.
15
Impossible.
Impossible.
Impossible.
Impossible.
``````
Best regards.
shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:
Thanx a lt. Got AC.
Shihab
CSE,BUET