10582 - ASCII Labyrinth

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

Moderator: Board moderators

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

10582 - ASCII Labyrinth

Post by titid_gede » Mon Dec 22, 2003 1:13 pm

hi,

what is the output for :

Code: Select all

3
1 1
+---+
|   |
|   |
|   |
+---+
1 1
+---+
| * |
| * |
| * |
+---+
2 2
+---+---+
|   |   |
|   |** |
|   | * |
+---+---+
|   |   |
|   |   |
|   |   |
+---+---+  
thanks in advance :)

-titid-
Kalo mau kaya, buat apa sekolah?

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Thu Dec 25, 2003 2:16 pm

My accepted solution outputs:
Number of solutions: 0
Number of solutions: 2
Number of solutions: 0
Which looks quite trivial :wink:
JongMan @ Yonsei

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Thu Dec 25, 2003 5:38 pm

thanks, got AC now. :) :)
Kalo mau kaya, buat apa sekolah?

domino
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 pm

Help

Post by domino » Thu Dec 25, 2003 6:04 pm

Could someone please post some more testcases, as i cannot get accepted...

domino
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 pm

Please help me

Post by domino » Sun Dec 28, 2003 6:54 pm

I have tried solving 10582 by backtracking, but i get wrong answer. Can somebody give me some hard testcases or a source code? Should i post my code?

Md. Sajjad Hossain
New poster
Posts: 9
Joined: Sat Jan 19, 2002 2:00 am
Location: Bangladesh

Post by Md. Sajjad Hossain » Tue Dec 30, 2003 9:00 pm

shouldn't there be a special judge ?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Wed Dec 31, 2003 2:49 am

hi,

to domino : i also use backtrack. i dont think there will be trickies input, except input i asked (in this thread) was confused me at first.
to mohd sajjad hossain : why do you think need special judge? i think it has unique result.
Kalo mau kaya, buat apa sekolah?

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Wed Dec 31, 2003 3:02 pm

One tricky input could have been

Code: Select all

+---+
|   |
|** |
| * |
+---+
where Number of solutions: 4 (or what else?).. but it is NOT present in the input data ;).
btw. the second input given by titid_gede isn't valid i think...

Code: Select all

1 1 
+---+ 
| * | 
| * | 
| * | 
+---+ 
because as the problem states... all the patterns should be in the `initial' form where

there are exactly three valid initial patterns for a square.
happy new year :D
Istiaque Ahmed [the LA-Z-BOy]

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Apr 23, 2004 4:42 am

For

Code: Select all

1 1
+---+
|   |
|** |
| * |
+---+
I get:

Code: Select all

Number of solutions: 2

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Fri Apr 23, 2004 11:28 am

I think it should be four, because the number of solution counts as
whether one can turn the pieces in such a way that the patterns form a line connecting some edge of the top left square and some edge of the bottom right square of the board.
so the four solutions would be...

Code: Select all

+---+
| * |
|** |
|   |
+---+

+---+
| * |
| **|
|   |
+---+

+---+
|   |
|** |
| * |
+---+

+---+
|   |
| **|
| * |
+---+
Note that the same square is the top left and bottom right square. And for each solution it satisfies the constrains that a line connects some edge of the top left square with some edge of bottom right square. The solution would have been 2 if you assume the fact as "line connects top/left edge of top left square and bottom/right edge of the bottom square". But this is not stated in the problem statement i think.
thank you.
Istiaque Ahmed [the LA-Z-BOy]

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Apr 23, 2004 9:53 pm

Well, then we know such inputs don't exist, because that's what I assume.. =)

alzika
New poster
Posts: 3
Joined: Sun Dec 11, 2005 7:24 am

10582

Post by alzika » Sun Dec 11, 2005 7:27 am

How do I even attempt this problem? I know it is backtracking, and that part is rather easy, but I'm not sure how to handle the backtracking portion involving the rotations and keeping track, as well as finding the NUMBER of solutions instead of just finding if there is a path at all.

Any assitance or a nudge in the right direction is appreciated.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10582

Post by Martin Macko » Sun Dec 11, 2005 12:44 pm

alzika wrote:How do I even attempt this problem? I know it is backtracking, and that part is rather easy, but I'm not sure how to handle the backtracking portion involving the rotations
In every step you can remember how you are rotated. There are four possible rotations. Let's denote them by numbers 0, 1, 2 and 3. After applying square A the rotation doesn't change. After applayng square B the rotation changes by +1 and -1 (mod 4). Then you move to the new position according to your new rotation.

Code: Select all

square A    square B

  ***         **
               *
alzika wrote:and keeping track
You can remember in an array which squares the path is already crossing.
alzika wrote:as well as finding the NUMBER of solutions instead of just finding if there is a path at all.
Don't just stop after you've found one path, but continue (by backtracking) to find all the paths.

alzika
New poster
Posts: 3
Joined: Sun Dec 11, 2005 7:24 am

Post by alzika » Mon Dec 12, 2005 2:06 am

Thanks.

Your assistance has led me to a greater outlook on this problem and I should be able to successfully complete it now.

alzika
New poster
Posts: 3
Joined: Sun Dec 11, 2005 7:24 am

Post by alzika » Fri Dec 16, 2005 9:00 am

The square A you have listed above, is there only 2 rotations for it, or 4? Meaning if it was the lower right corner square, should I count it twice for two different possible ways to arrive at the goal (if it has 4 rotations)?

Post Reply

Return to “Volume 105 (10500-10599)”