11531 - Solve the Broken Maze

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

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11531 - Solve the Broken Maze

Post by brianfry713 » Fri Nov 22, 2013 12:13 am

AC output for DeadLock's input is Don't Try., I don't see how it could be Try.

You can't visit a block more than once.

First try solving https://www.spoj.pl/problems/MAZE/
You should then be able to expand your code to solve 11531.

DFS will TLE.

I solved it in O(N) using DP. The states I used were a 4 bit bool array that keeps track of which rows are reachable going right from the left edge, and whether you can bend back left and connect rows 1 and 2 (coming from row 3 or 4), 1 and 3 (coming from row 4), 2 and 3 (coming from row 1 or 4), 2 and 4 (coming from row 1), or 3 and 4 (coming from row 1 or 2). My code is 471 lines and considers each of the 81 possible columns, some are grouped together.

To debug I wrote a DFS solver function and compared to my DP code all possible inputs up to N = 6.

My code has 223 reachable states.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 115 (11500-11599)”