TREEMAZE - Perfect Maze

 

Hi Guys,
Yesterday my nephew visited me and we played with lego. We decided to create castle with maze.
We took board of 5 x 5 and created different mazes. We decided that we need perfect maze - One that has minimum lego pieces, but there should be exactly one path between each pair of cells without lego.
We quickly find out that we need just 6 pieces and build all 22 configurations using them
Some of them:

Hi Guys,

Yesterday my nephew visited me and we played with lego.

We took board of 5 x 5 and created different mazes. We decided that we need perfect maze - One that has minimum lego pieces, but there should be exactly one path between each pair of cells without lego.

We quickly found out that we needed just 6 pieces and built all 22 configurations using them

 

Some of them:

 

Maze

But then he took his board of 13 x 13 and said - let's build perfect maze here!

Now we have no idea how many pieces we need and how many configurations we should build. Please help!

 

 

Output

Two numbers - number of single lego pieces we need to build perfect maze on 13x13 board and number of configurations of them.

 

Thanks!

 

 


Added by:Oleg
Date:2011-07-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:TEXT

hide comments
2017-11-26 13:31:41
Can anyone hint about the algo required for this?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.