949 - Getaway

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

Moderator: Board moderators

Post Reply
Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

949 - Getaway

Post by Emilio » Fri Dec 15, 2006 5:31 pm

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!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Dec 15, 2006 9:08 pm

My accepted code returns...

Output:

Code: Select all

6
4
0
1
3
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Fri Dec 15, 2006 9:33 pm

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!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 949 - Getaway

Post by brianfry713 » Thu Apr 05, 2012 10:32 pm

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
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 949 - Getaway

Post by Mukit Chowdhury » Sat Sep 21, 2013 7:36 am

Accepted.... :)
Last edited by Mukit Chowdhury on Sat Oct 19, 2013 5:41 pm, edited 3 times in total.

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 949 - Getaway

Post by Mukit Chowdhury » Sat Sep 21, 2013 10:31 am

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 ???

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 949 - Getaway

Post by brianfry713 » Fri Oct 11, 2013 8:48 pm

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
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 949 - Getaway

Post by Mukit Chowdhury » Sat Oct 19, 2013 3:12 pm

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 949 - Getaway

Post by brianfry713 » Fri Feb 06, 2015 8:16 pm

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]
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 9 (900-999)”