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

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

10977 - Enchanted Forest

Post by rushel » Wed Dec 28, 2005 8:12 pm

I tried to solve this problem using bfs and i had lot of WA
Can anyone give me some tricky case .
Please Help.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Wed Dec 28, 2005 8:15 pm

if your starting position[1,1] is blocked, you cannot reach the destination
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Sub

Post by rushel » Wed Dec 28, 2005 8:18 pm

I checked that but what about the pokemon which area it covers ( horizontal, vertical, diagonal) isnt it.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Wed Dec 28, 2005 8:41 pm

the total area blocked by jigglipuff is circular area. you have to find very carefully the intersections she blocked.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel » Wed Dec 28, 2005 8:50 pm

Thanks. I thought that in contest time but i am not good at geom. Thanks For ur help.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Thu Dec 29, 2005 8:39 am

somebody check my code.. please.. ;;
i do BFS..
and don't know why WA..


if position (i, j) is blocked, i checked map[j] = 1


Code: Select all

CUT AFTER AC
Last edited by helloneo on Thu Dec 29, 2005 12:23 pm, edited 2 times in total.

Koo Kyung-ryeol
New poster
Posts: 1
Joined: Thu Dec 29, 2005 8:47 am
Location: ICU, Korea

Post by Koo Kyung-ryeol » Thu Dec 29, 2005 8:50 am

Code: Select all

                        printf("Impossible\n");
For each case, if some "dangerous" places are unavoidable, print "Impossible."

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

Post by Darko » Thu Dec 29, 2005 9:30 am

Yes, that was the only mistake in that code.

Now, I think my BFS is exactly the same, but it keeps timing out (in Java):

Code: Select all

	private int bfs() {
		queue.addElement(new Sq(0, 0, 0));
		grid[0][0] = 1;
		while (!queue.isEmpty()) {
			Sq curr = (Sq) queue.elementAt(0);
			queue.removeElementAt(0);
			int i = curr.i;
			int j = curr.j;
			if (i == r - 1 && j == c - 1) {
				queue.removeAllElements();
				return curr.dist;
			}
			if (i < r - 1 && grid[i + 1][j] == 0) {
				queue.addElement(new Sq(i + 1, j, curr.dist + 1));
				grid[i + 1][j] = 1;
			}
			if (j < c - 1 && grid[i][j + 1] == 0) {
				queue.addElement(new Sq(i, j + 1, curr.dist + 1));
				grid[i][j + 1] = 1;
			}

			if (i > 0 && grid[i - 1][j] == 0) {
				queue.addElement(new Sq(i - 1, j, curr.dist + 1));
				grid[i - 1][j] = 1;
			}
			if (j > 0 && grid[i][j - 1] == 0) {
				queue.addElement(new Sq(i, j - 1, curr.dist + 1));
				grid[i][j - 1] = 1;
			}
		}
		return -1;
	}

Sq is just Point with distance from (0,0).

Note that the queue above is actually Vector (has some sync overhead, but is still not that bad). We can't use any other built-in types on OJ (except Hastable), so it is kind of fun.

From what I gathered, it takes 0.2 secs per grid! (Not at my home PC, those 19900 path grids take the longest - 0.01sec, otherwise, it can do ~1000 empty 200x200 in sec)

I tried inserting points that are closer to the end in front of the queue(sort of A*), but that didn't change it much.

I used exactly the same BFS algorithm to fill in 10267, I didn't run out of time there.

Can I improve it somehow? Or is it just OJ Java thing?

Darko

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Thu Dec 29, 2005 12:09 pm

..
Last edited by helloneo on Tue May 22, 2007 8:03 am, edited 1 time in total.

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

10977 - Enchanted Forest

Post by shihabrc » Thu Dec 29, 2005 2:08 pm

I don't know why i'm getting RTE for this prob.(there is no chance of array overrun or negetive indexing,though my memory management is not that efficient) It made me really mad during the contest. Still now i can't find the problem . Plaeaaz somebody help.

Code: Select all

Cut
-Shihab
Last edited by shihabrc on Tue Jan 17, 2006 11:09 pm, edited 1 time in total.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Thu Dec 29, 2005 4:41 pm

If you think you don't enqueue more than 500 times, then you are wrong.

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

Still getting RTE

Post by shihabrc » Thu Dec 29, 2005 9:42 pm

Sorry. I've changed the size of que to 40100, which is large enough to hold 200x200 points.(according to the prob statement the forest will be at most 200x200 grid.) But i'm still getting RTE. Pleaz help me.
Shihab
CSE,BUET

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Thu Dec 29, 2005 9:51 pm

Actually your queue should be big enough to hold maximum vertices that can be considered at the same time which is correctly 200*200. But you may enqueue more than that. You have made a linear queue. Try to make queue circular always. Just update the tail and head by modding it with the size.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Dec 29, 2005 10:19 pm

Or only enqueue when it's not in the queue, which is good enough.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » Fri Dec 30, 2005 7:44 am

ayon wrote:the total area blocked by jigglipuff is circular area. you have to find very carefully the intersections she blocked.
I got WA.
I may be misunderstanding about the dangerous area covered by Jigglypuff.
Then, I make a following test case.
Is my idea wrong?

Code: Select all

10 10
4
1 5
2 3
4 1
8 10
4
3 2 0
5 6 3
10 1 4
10 8 1
0 0
And following is an image in my mind.
'0' is safe area, '1' is dangerous area or blocked position.

0000100000
0010010000
0100111000
1001111100
0011111110
1001111100
1100111000
1110010001
1111000100
1111101110

So, I think the answer is 24.

Thank you.

Post Reply

Return to “Volume 109 (10900-10999)”