949 - Getaway

[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!

[Jan]

My accepted code returns...

Output:

Code: Select all

6
4
0
1
3

Hope it helps.

[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!

[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

[Mukit Chowdhury]

Accepted....

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

[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

[Mukit Chowdhury]

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]

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]