/*
Author : Anand Krishnamoorthi
Compiling:
MSVC: cl /EHsc /O2 HamiltonianCycles.cpp
GCC : g++ O2 HamiltonianCycles.cpp o HamiltonianCycles
Usage:
HamiltonianCycles rows cols
Based on my solution to the Quora Datacenter Cooling Challenge.
Description of the problem: http://www.quora.com/challenges#datacenter_cooling
Description of the original solution:
An elegant, ultra fast solution to the Quora Datacenter Cooling Challenge.
In a valid layout of the duct through the rooms in the datacenter:
1) Every room must have exactly 2 connections/edges.
Rooms that we own "0" must have an incoming and an outgoing edge.
Start room "2" must have an outgoing edge and an imaginary incoming edge.
End room "3" must have an incoming edge and an imaginary outgoing edge.
Rooms that we don't own "1" are assumed to already have 2 edges.
2) There are no cycles. The following layout is not valid.
2 00
  
0 00

003
Every room above has two edges, but the four rooms in topright form a cycle.
They are not part of the path from room "2" to "3".
"A valid layout of the duct is one in which each room has two edges and there are no cycles."
Edges can be thought to be directionless for layout.
There are 4 possible edges that a room can have:
UP

LEFT  Rm  RIGHT

DOWN
The LEFT edge of a room is the RIGHT edge of the room to it's left.
The UP edge of a room is the DOWN edge of the room above it.
If we process the rooms left to right, top to bottom, starting with the room at
the topleft corner, then we only need to consider the RIGHT and DOWN edges of a room.
The top edge of a room would've been handled when the room immediately above it, in the
preceeding row, was processed. Similarly the left edge of the room would already have been
handled when the room immediately to the left, in the current row, was processed.
An unprocessed room would look like following:
 
 Rm (Or) Rm (Or)  Rm (Or) Rm
(Case A) (Case B) (Case C) (Case D)
In Case A, the room already has 2 connections and we can skip to the next room.
In Case B and Case C, the room has just one connection and we need to add one more if the room is "0".
In Case D, the room has no connections and we must add 2 connections (just 1 if it is "2" or "3").
If an unprocessed room has no connections (Case D), then we must connect it both to the right and down:
Rm 

If and unprocessed room has just one connection, then we need to connect it first to the right, continue solving,
then remove the connection and reconnect down to the room below and then solve.
Preventing Cycles:
A cycle is only formed when a room is connected to the room on its right and there's already a path from the room to
the room on its right:
0  0  0  0 0  2
  
0 1 0  0 0 1
  
0  0 0 0 0 1
R0 R1 R2 R3 R4
In the above example, there's already a path from R1 to R2, so connecting R1 right to R2 would lead to a cycle.
Therefore to prevent cycles, we need to keep track of the end point (ending room) of the path from a room.
0  0  0  0 0  2
  
0 1 0  0 0 1
  
0 0 0 0 0 1
R0 R1 R2 R3 R4
In the above example, the pathendpoint of R0 is R2 and viceversa.
The endpoint of "2" is R4 and viceversa.
When we make a new connection, we update the endpoints:
0  0  0  0 0  2
  
0 1 0  0 0 1
  
0  0 0 0 0 1
R0 R1 R2 R3 R4
After connecting R0 right to R1, the pathendpoint of R1 is R2 and that of R2 is now R1.
We don't really care about of endpoint of R0 at this point.
This approach also automatically merges two paths when a connection is made.
2 0  0  0
  
0 0 0 0
R0 R1 R2 R3
In the above example, the endpoint of R0 is "2" and viceversa.
The endpoint of R1 is R3 and viceversa.
When we connect R0 to R1 (this does not introduce a cycle is endpoint of R1 is not R0),
we get the endpoints of R0 and R1 and make them "endpoint" eachother.
2 0  0  0 e1 < endpoint(R0)
   e2 < endpoint(R1)
0  0 0 0 endpoint(e1) < e2
R0 R1 R2 R3 endpoint(e2) < e1
After connecting R0 to R1 and performing updates as described above, endpoint of "2" is R3 and viceversa.
When a connection is removed, we restore the endpoints of the rooms.
Memoization
"Rooms in a row that is just about to be processed have paths from "2", "3" or other rooms in that row."
Row 0 : 2 0  0  0  0 2  0 0  0  0
     
Row 1: 0 0  0 3 0 0  0 0 3 0
       
Row 2: 0 0 0 0 0 0 0 0 0 0
R0 R1 R2 R3 R4 R0 R1 R2 R3 R4
(layout A) (layout B)
In the above example, we've finished processing Row 1 and are about to process Row 2.
R0 has a path from "2", R3 has a path to "3".
R1 (has an imaginary path to itself), R2 and R4 all have paths to other rooms in the same row.
The algorithm relies *only* on the pathend of rooms and the number of connections.
This means that processing Row 2 in layout A and in layout B would produce the same results.
The pathends of rooms in an unprocessed row uniquely identifies it in the context of a partial solution.
It doesn't matter how the paths themselves are laid out, only the pathends matter.
So the list of pathends of (the next) unprocessed row, can be used as key in a cache used for memoization.
So the result of processing Row 2 in layout A can be memoized and later reused while processing
Row 2 in layout B.
Efficient Memoization
A backtracking solution with memoization would (if implemented for maximum speed) put all the valid pathend combinations
of all the rows in the cache. The backtracking solution keeps recursing from Row 0 to Row R, then backup to Row 0 and again
to Row R (where R is the number of rows). This gets memory intensive with a large grid like 14x14.
To be memory efficient, we can process strictly rowwise. Rather than processing the next (unprocessed) row immediately after a
row has been processed, we can put the unprocessed row in a work list for later processing. We go back to solving the current row,
generating all possible valid pathend combinations for the next row. Once we are completely done with the current row, we
move on to the next row. The next row becomes the current row.
We take each pathend combination from the worklist, apply it back on to the row and process the row, generating valid pathend combinations
for the new next row.
*/
#if defined(__GCC__)
#define FORCE_INLINE __attribute__((always_inline))
#elif defined(_MSC_VER)
#define FORCE_INLINE __forceinline
#define _SECURE_SCL 0
#define _HAS_ITERATOR_DEBUGGING 0
#else
#define FORCE_INLINE inline
#endif
#include
#include
#include
#include