## 949 - Getaway

Moderator: Board moderators

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

### 949 - Getaway

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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
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

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

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

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

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

Accepted ...

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

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!