EPIC1305 - Longest Maze Path

A maze can have multiple solution paths from start to finish.  In this example you can see that there are two distinct solutions that do not cross the same position twice.

 

 

Given a maze, find the longest path from start to finish that does not cross the same position twice.  If there is no solution, return zero.

Note that the maze dimensions will be small enough that you can store it with unsigned 32-bit integers.

Input

Each maze is defined as follows:

  1. A row begins with a coordinate pair (X,Y).
  2. After the coordinate pair, between zero-to-four coordinates are listed.  This defines the connected paths from the initial coordinate and the following coordinate(s).
  3. Optionally, the line may end with an "s" or "e".
    • 's' signifies the starting square for the maze.
    • 'e' signifies the ending square for the maze.

Output

The length of the longest path through the maze that does not cross the same position twice.  You should count the start and end positions.

Example

Input:
(1,1),(1,2)(2,1)
(2,1),(1,1)(2,2)(1,3)e
(3,1),(2,1)(4,1)
(4,1),(3,1)(4,2)
(1,2),(1,1)(1,3)
(2,2),(2,1)
(3,2),(4,2)(3,3)
(4,2),(4,1)(3,2)
(1,3),(1,2)(1,4)
(2,3),(2,4)
(3,3),(3,2)(4,3)
(4,3),(3,3)(4,4)
(1,4),(1,3)(1,5)(2,4)
(2,4),(1,4)(2,3)(2,5)(3,4)
(3,4),(2,4)(4,4)
(4,4),(4,3)(3,4)(4,5)
(1,5),(1,4)
(2,5),(2,4)s
(3,5),(4,5)
(4,5),(3,5)(4,4) Output: 11

Added by:BYU Admin
Date:2013-03-20
Time limit:2s-15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-11-08 10:07:59 Min_25
Note: A brute force algorithm works.

Last edit: 2015-02-14 01:32:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.