710 - The Game

[Dmytro Chernysh]

I read the description MANY times, but I can't get the Judge's output.
Maybe it's wrong?
Can somebody ilustrate me the answer?

[Dmytro Chernysh]

No one can explain to me?
Maybe nobody understands either?

[Dominik Michniewski]

I think, that judge's answer is NUMBER of LINE SEGMENTS, which connect to given points but I get WA ...

Maybe other people could give us some IO tests ?

Best regards
DM

[little joey]

Yes, it's the number of line segments (or the number of 90 degree turns Plus one). Did you notice that the input is given x1 y1 x2 y2, that is col1 row1 col2 row2, just the other way around than you'd normaly expect?
I can't think of special cases. Here's the complete list for the (1,1) piece in the example:

Code: Select all

5 4
XXXXX
X   X
XXX X
 XXX 
1 1 2 1
1 1 3 1
1 1 4 1
1 1 5 1
1 1 1 2
1 1 1 5
1 1 1 3
1 1 2 3
1 1 3 3
1 1 3 5
1 1 2 4
1 1 3 4
1 1 4 4
0 0 0 0
0 0

And the answer is:

Code: Select all

Board #1:
Pair 1: 1 segments.
Pair 2: 3 segments.
Pair 3: 3 segments.
Pair 4: 3 segments.
Pair 5: 1 segments.
Pair 6: 3 segments.
Pair 7: 3 segments.
Pair 8: impossible.
Pair 9: impossible.
Pair 10: 4 segments.
Pair 11: 3 segments.
Pair 12: impossible.
Pair 13: 4 segments.

[sohel]

I can't seem to understand the 10th and 12th case that 'Little Joey' Posted.
Is the input coordinate 1 1 3 5 valid.. bcos I think 3 5 is not a position of a card.
and why is it 'impossible for the 12th .. since you can go out of the board can't you reach the destination.

[little joey]

You are completely right, sohel. I must have had an off day back then
The input file was wrong and contained illegal pieces.
Here is the correct input (I hope ...)

Code: Select all

5 4
XXXXX
X   X
XXX X
 XXX 
1 1 2 1
1 1 3 1
1 1 4 1
1 1 5 1
1 1 1 2
1 1 5 2
1 1 1 3
1 1 2 3
1 1 3 3
1 1 5 3
1 1 2 4
1 1 3 4
1 1 4 4
0 0 0 0
0 0

And the output:

Code: Select all

Board #1:
Pair 1: 1 segments.
Pair 2: 3 segments.
Pair 3: 3 segments.
Pair 4: 3 segments.
Pair 5: 1 segments.
Pair 6: 4 segments.
Pair 7: 3 segments.
Pair 8: impossible.
Pair 9: impossible.
Pair 10: 4 segments.
Pair 11: 3 segments.
Pair 12: 4 segments.
Pair 13: 4 segments.

[sohel]

Thanks for the rectification. Now the output matches with that of mine but i am getting WA.

I used BFS. While pushing into Queue I did not add any cost if it came from the same direction. Ie from 2 2 to 3 2 then to 4 2 would require one move. Is there anyting wrong.

[little joey]

I use a modification of floodfill, which is a kind of BFS too. In principle your program should work.
What is your answer for the following case:

Code: Select all

14 7
XXXXXXXXXXXXXX
XX           X
X XXXXXXXXXX X
X XX         X
X  XX        X
XX           X
XXXXXXXXXXXXXX
2 2 5 5
0 0 0 0
0 0

It should be 3, not 5. That's the only kind of tricky case I can think of.
(Hope I got my numbers right this time...)

[sohel]

Just got Ac.
My program actually gave 5 as the answer. I made the necessary modification and got AC.
Thanks, nevertheless.

[Shmuma]

I'm trying to solve this problem and constantly get WA.

I've checked all tests in this topic, could anyone post another tests?

Upd: got AC. Just output 'Impossible.' instead of 'impossible.'

[DD]

You are completely right, sohel. I must have had an off day back then
The input file was wrong and contained illegal pieces.
Here is the correct input (I hope ...)

Code: Select all

5 4
XXXXX
X X
XXX X
XXX 
1 1 2 1
1 1 3 1
1 1 4 1
1 1 5 1
1 1 1 2
1 1 5 2
1 1 1 3
1 1 2 3
1 1 3 3
1 1 5 3
1 1 2 4
1 1 3 4
1 1 4 4
0 0 0 0
0 0

And the output:

Code: Select all

Board #1:
Pair 1: 1 segments.
Pair 2: 3 segments.
Pair 3: 3 segments.
Pair 4: 3 segments.
Pair 5: 1 segments.
Pair 6: 4 segments.
Pair 7: 3 segments.
Pair 8: impossible.
Pair 9: impossible.
Pair 10: 4 segments.
Pair 11: 3 segments.
Pair 12: 4 segments.
Pair 13: 4 segments.

It is quite interesting that my outputs are different from yours , but I also got A.C.
My output:

Code: Select all

Board #1:
Pair 1: 1 segments.
Pair 2: 3 segments.
Pair 3: 3 segments.
Pair 4: 3 segments.
Pair 5: 1 segments.
Pair 6: 4 segments.
Pair 7: 3 segments.
Pair 8: 6 segments.
Pair 9: 5 segments.
Pair 10: 4 segments.
Pair 11: 4 segments.
Pair 12: 4 segments.
Pair 13: 4 segments.

I think the main reason for this phenomenon is that we have different definitions for boundary. But it also points out that the judge didn't have such test cases which needs to use the leftmost and rightmost boundary.

[Hikari9]

For all solvers, do take note that the only moves you can do are left turn, right turn, and straight.