10977 - Enchanted Forest

[rushel]

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

[ayon]

if your starting position[1,1] is blocked, you cannot reach the destination

[rushel]

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

[ayon]

the total area blocked by jigglipuff is circular area. you have to find very carefully the intersections she blocked.

[rushel]

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

[helloneo]

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

[Koo Kyung-ryeol]

Code: Select all

                        printf("Impossible\n");

For each case, if some "dangerous" places are unavoidable, print "Impossible."

[Darko]

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]

..

[shihabrc]

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

[mamun]

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

[shihabrc]

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.

[mamun]

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]

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

[tan_Yui]

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.