## 710 - The Game

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

Moderator: Board moderators

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

### 710 - The Game

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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
No one can explain to me?
Maybe nobody understands either?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Not Clear!

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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Still WA

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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### thanx

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

Shmuma
New poster
Posts: 1
Joined: Thu Sep 20, 2007 4:35 pm
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
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 710 - The Game

little joey wrote: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.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Hikari9
New poster
Posts: 20
Joined: Tue Jan 22, 2013 4:39 pm

### Re: 710 - The Game

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