Page 1 of 1

949 - Getaway

Posted: Fri Dec 15, 2006 5:31 pm
by Emilio
Hi all,

Im trying to solve this problem but im getting WA. So, i dont know if i dont understand something in the statement problem, im missing something, i have a(or more than one) bug, ...
So, in order to try clear my doubts, could anyone give the correct output for this test cases, and even better could be if anyone give some extra test cases.

Code: Select all

3 3
6
0 0 1 0
1 0 0 0
1 0 2 0
0 1 0 2
1 2 0 2
1 2 2 2
2
2 1 1
4 2 1

4 2
10
1 0 0 0
0 1 0 0
1 1 1 0
0 2 1 2
1 2 0 2
1 1 0 1
0 3 0 2
1 3 1 2
1 3 0 3
1 2 1 1
5
1 1 0
2 0 2
3 1 2
4 0 3
5 1 3

1 1
0
0

1 2
0
4
1 1 0
2 1 0
3 1 0
4 1 0

4 1
3
0 1 0 0
0 2 0 1
0 3 0 2
2
2 0 2
3 0 1
Thanks in advance!

Posted: Fri Dec 15, 2006 9:08 pm
by Jan
My accepted code returns...

Output:

Code: Select all

6
4
0
1
3
Hope it helps.

Posted: Fri Dec 15, 2006 9:33 pm
by Emilio
Thanks, i got AC
stupid of me, i solved with 3 different approachs, but i didnt feel the change of rows and colums in this problem, which is not the most typical!

Re: 949 - Getaway

Posted: Thu Apr 05, 2012 10:32 pm
by brianfry713
For future reference, the input posted above is invalid. All x values are less than the number of vertical roads nv and all y values are less than the number of horizontal roads. Here is the input Emilio posted corrected:

Code: Select all

3 3
6
0 0 1 0
1 0 0 0
1 0 2 0
0 1 0 2
1 2 0 2
1 2 2 2
2
2 1 1
4 2 1

2 4
10
1 0 0 0
0 1 0 0
1 1 1 0
0 2 1 2
1 2 0 2
1 1 0 1
0 3 0 2
1 3 1 2
1 3 0 3
1 2 1 1
5
1 1 0
2 0 2
3 1 2
4 0 3
5 1 3

1 1
0
0

2 1
0
4
1 1 0
2 1 0
3 1 0
4 1 0

1 4
3
0 1 0 0
0 2 0 1
0 3 0 2
2
2 0 2
3 0 1
My AC output for this input:

Code: Select all

6
6
0
5
4

Re: 949 - Getaway

Posted: Sat Sep 21, 2013 7:36 am
by Mukit Chowdhury
Accepted.... :)

Re: 949 - Getaway

Posted: Sat Sep 21, 2013 10:31 am
by Mukit Chowdhury
What is the output for the input given below...

Code: Select all

2 1
0
1
0 0 0
My code posted here shows "2" & it is WA... is it correct ???

Re: 949 - Getaway

Posted: Fri Oct 11, 2013 8:48 pm
by brianfry713
I don't think the input you posted is valid. There is always a possible escape route.

Try input:

Code: Select all

1 2
0
2
0 0 1
1 0 1
AC output:

Code: Select all

2

Re: 949 - Getaway

Posted: Sat Oct 19, 2013 3:12 pm
by Mukit Chowdhury
Accepted ... :D

Thanks brianfry713... Though your case was the key... But while checking for your input, I've found another error... :)
That case is...

Code: Select all

2 2
0
2
1 0 1
2 0 1
output is...

Code: Select all

2

Re: 949 - Getaway

Posted: Fri Feb 06, 2015 8:16 pm
by brianfry713
There is a restriction in the judge's input that is not valid, my AC code ignores it.
if(x1 + 1 == x2 && y1 == y2) restrict east
else if(x1 - 1 == x2 && y1 == y2) restrict west
else if(x1 == x2 && y1 + 1 == y2) restrict south
else if(x1 == x2 && y1 - 1 == y2) restrict north
else do nothing

I solved it using BFS. If the next intersection is monitored at that time, then also try staying in your current location. I keep track of the intersections monitored using an array: int m[501][2]