10977 - Enchanted Forest

[Darko]

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]

Well actually the case is not valid, since loudness >= 1 (Read the problem description again...)

[Darko]

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]

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]

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.

[shihabrc]

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

[Solaris]

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.

[mamun]

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]

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]

Code: Select all

####### 
#S##### 
#____## 
#__#__# 
#_#X#_# 
#__#_F# 
####### 

You must take into account Jigglypuff and its loudness.
Its loudness is circular.

[StatujaLeha]

Emilio, Did I understand right that Euclidean distance is a distance between centers of places?

[StatujaLeha]

Emilio, thanks for you explanation. I got Acc.

[shihabrc]

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
	

[tan_Yui]

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]

Thanx a lt. Got AC.