11531 - Solve the Broken Maze

[brianfry713]

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.