10977 - Enchanted Forest

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Dec 30, 2005 8:01 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

Post by Observer » Fri Dec 30, 2005 8:11 am

Well actually the case is not valid, since loudness >= 1 (Read the problem description again...) :wink:
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
Location: Calgary, Canada

Post by Darko » Fri Dec 30, 2005 8:24 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

Post by tan_Yui » Fri Dec 30, 2005 10:04 am

Thanks, Darko and Observer.
Finally, I could get Accepted :D

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
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Fri Dec 30, 2005 12:03 pm

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

Post by shihabrc » Fri Dec 30, 2005 9:09 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Sat Dec 31, 2005 9:04 am

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
Location: Bangladesh
Contact:

Post by mamun » Sat Dec 31, 2005 12:23 pm

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

Post by StatujaLeha » Tue Jan 03, 2006 2:01 am

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

Post by Emilio » Tue Jan 03, 2006 2:15 am

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

Post by StatujaLeha » Tue Jan 03, 2006 12:12 pm

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

Post by StatujaLeha » Tue Jan 03, 2006 12:24 pm

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:

Post by shihabrc » Tue Jan 17, 2006 11:21 pm

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

Post by tan_Yui » Thu Jan 19, 2006 1:30 pm

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:

Post by shihabrc » Sun Jan 22, 2006 2:57 am

Thanx a lt. Got AC. :D
Shihab
CSE,BUET

Post Reply

Return to “Volume 109 (10900-10999)”