// victorique0.cc - Don Yang (uguu.org)
//
// 04/17/11

#include<stdio.h>
#include<string.h>
#include<queue>
#include<set>
#include<string>
using namespace std;

// Puzzle definition
static const char *kStart[] =
{
   "baac",
   "baac",
   "dffe",
   "dghe",
   "i..j"
};
static const char *kGoal[] =
{
   "....",
   "....",
   "....",
   ".aa.",
   ".aa."
};
static const int kHeight = sizeof(kStart) / sizeof(kStart[0]);
static const int kWidth = 4;

// Set of all states that has been observed (key=fingerprint)
typedef set<string> SeenNodes;

// Character that specifies which cell is empty
static const unsigned char kEmpty = '.';

// Block types.  Suffixes denote width and height.
enum BlockType
{
   UNUSED = 0,
   BLOCK_11,
   BLOCK_12,
   BLOCK_21,
   BLOCK_22,
   EMPTY
};
static BlockType block_type[256];

// A single puzzle state
class Node
{
public:
   // Initialize pointer to parent node
   explicit Node(const Node *parent) : parent_(parent)
   {
      if( parent != NULL )
         memcpy(cell_, parent->cell_, kHeight * kWidth);
   }

   // Swap two cells
   void Swap(int x0, int y0, int dx, int dy)
   {
      const unsigned char tmp = cell_[y0][x0];
      cell_[y0][x0] = cell_[y0 + dy][x0 + dx];
      cell_[y0 + dy][x0 + dx] = tmp;
   }

   // Read a single cell, returning 0 for out of bounds cells
   inline char Get(int x, int y) const
   {
      return (y >= 0 && y < kHeight && x >= 0 && x < kWidth) ? cell_[y][x] : 0;
   }

   // Get block type for a single cell
   inline BlockType GetType(int x, int y) const
   {
      return block_type[static_cast<int>(Get(x, y))];
   }

   // Check if this node is the terminal state, returns true if so
   bool Goal() const
   {
      for(int y = 0; y < kHeight; y++)
      {
         for(int x = 0; x < kWidth; x++)
         {
            if( kGoal[y][x] != kEmpty && cell_[y][x] != kGoal[y][x] )
               return false;
         }
      }
      return true;
   }

   // Compute fingerprint for hashing
   string GetFingerprint() const
   {
      string fingerprint;
      fingerprint.reserve(kHeight * kWidth);
      for(int y = 0; y < kHeight; y++)
         for(int x = 0; x < kWidth; x++)
            fingerprint.push_back(static_cast<int>(block_type[cell_[y][x]]));
      return fingerprint;
   }

   // Accessor and mutator
   inline const Node *parent() const { return parent_; }
   inline void SetCell(int x, int y, char c) { cell_[y][x] = c; }

private:
   const Node *parent_;
   unsigned char cell_[kHeight][kWidth];
};

// List of nodes
typedef queue<Node*> NodeQueue;

// {{{ Display

// Decide which string to output at a particular cell
const char *Cell(const Node &node, int x, int y)
{
   return node.Get(x, y) == kEmpty ? "::" : "  ";
}

// Decide which character to output at a particular corner
char Corner(const Node &node, int x, int y)
{
   if( node.Get(x - 1, y - 1) == node.Get(x, y - 1) )
   {
      // +-----+  +-----+  +-----+
      // |     |  |     |  |     |
      // |     |  +-----+  +--+--+
      // |     |  |     |  |  |  |
      // +-----+  +-----+  +-----+
      if( node.Get(x - 1, y) == node.Get(x, y) )
      {
         if( node.Get(x - 1, y - 1) == node.Get(x - 1, y) )
            return *Cell(node, x, y);
         else
            return '-';
      }
      else
      {
         return '+';
      }
   }
   else
   {
      // +--+--+  +--+--+  +--+--+  +--+--+
      // |  |  |  |  |  |  |  |  |  |  |  |
      // |  |  |  +--+--+  +--+  |  |  +--+
      // |  |  |  |  |  |  |  |  |  |  |  |
      // +--+--+  +--+--+  +-----+  +-----+
      if( node.Get(x - 1, y - 1) == node.Get(x - 1, y) &&
          node.Get(x, y - 1) == node.Get(x, y) )
      {
         return '|';
      }
      else
      {
         return '+';
      }
   }
}

// Decide which string to output at a particular horizontal edge
const char *HorizontalEdge(const Node &node, int x, int y)
{
   return node.Get(x, y - 1) == node.Get(x, y) ? Cell(node, x, y) : "--";
}

// Decide which character to output at a particular vertical edge
char VerticalEdge(const Node &node, int x, int y)
{
   return node.Get(x - 1, y) == node.Get(x, y) ? *Cell(node, x, y) : '|';
}

// Output a single node state
void OutputNode(const Node &node)
{
   string line;
   line.reserve(kWidth * 3 + 1);
   for(int y = 0; y < kHeight + 1; y++)
   {
      line.clear();
      for(int x = 0; x < kWidth; x++)
      {
         line.push_back(Corner(node, x, y));
         line.append(HorizontalEdge(node, x, y));
      }
      line.push_back(Corner(node, kWidth, y));
      puts(line.c_str());

      if( y < kHeight )
      {
         line.clear();
         for(int x = 0; x < kWidth; x++)
         {
            line.push_back(VerticalEdge(node, x, y));
            line.append(Cell(node, x, y));
         }
         line.push_back(VerticalEdge(node, kWidth, y));
         puts(line.c_str());
      }
   }
}

// Output path to solution
void OutputSolution(const Node &node, int *move)
{
   // Output parent node first.  If there is no parent node, it means
   // we are at the beginning of the solution chain.
   if( node.parent() != NULL )
      OutputSolution(*node.parent(), move);
   else
      *move = 0;

   // Output state at current node
   printf("Move %d\n", *move);
   OutputNode(node);
   ++*move;
}

// }}}

// {{{ Solver

// Initialize block types from input
void InitBlockTypes(const Node &root)
{
   block_type[kEmpty] = EMPTY;
   for(int y = 0; y < kHeight; y++)
   {
      for(int x = 0; x < kWidth; x++)
      {
         // Assign types to each block only once
         const int block = static_cast<int>(root.Get(x, y));
         if( block_type[block] != UNUSED )
            continue;

         // Assign type based on which neighbor cells this block spans.
         // Assume all blocks are rectangular, and will not span more
         // than 2 cells.
         block_type[block] =
            block == root.Get(x + 1, y)
               ? block == root.Get(x, y + 1) ? BLOCK_22 : BLOCK_21
               : block == root.Get(x, y + 1) ? BLOCK_12 : BLOCK_11;
      }
   }
}

// Add a neighbor node to queue if it's not a duplicate
void AddNeighbor(Node *node, SeenNodes *all_states, NodeQueue *output)
{
   const string fingerprint = node->GetFingerprint();
   if( all_states->insert(fingerprint).second )
      output->push(node);
   else
      delete node;
}

// Find all neighbors for a particular state, and enqueue all
// previously unobserved states.
void FindNeighbors(const Node *start, SeenNodes *all_states, NodeQueue *output)
{
   for(int y = 0; y < kHeight; y++)
   {
      for(int x = 0; x < kWidth; x++)
      {
         // Find empty spaces
         if( start->Get(x, y) != kEmpty )
            continue;

         // Try swap empty space with neighbors horizontally
         for(int dx = -1; dx <= 1; dx += 2)
         {
            const BlockType type = start->GetType(x + dx, y);
            if( type == BLOCK_11 )
            {
               Node *neighbor = new Node(start);
               neighbor->Swap(x, y, dx, 0);
               AddNeighbor(neighbor, all_states, output);
            }
            else if( type == BLOCK_21 &&
                     start->Get(x + dx, y) == start->Get(x + dx * 2, y) )
            {
               Node *neighbor = new Node(start);
               neighbor->Swap(x, y, dx * 2, 0);
               AddNeighbor(neighbor, all_states, output);
            }
            else if( type == EMPTY )
            {
               if( start->GetType(x + dx * 2, y) == BLOCK_11 )
               {
                  Node *neighbor = new Node(start);
                  neighbor->Swap(x, y, dx * 2, 0);
                  AddNeighbor(neighbor, all_states, output);
               }
               else if( start->GetType(x + dx * 2, y) == BLOCK_21 &&
                        start->Get(x + dx * 2, y) == start->Get(x + dx * 3, y) )
               {
                  Node *neighbor = new Node(start);
                  neighbor->Swap(x, y, dx * 2, 0);
                  neighbor->Swap(x + dx, y, dx * 2, 0);
                  AddNeighbor(neighbor, all_states, output);
               }
            }
         }

         // Try swap empty space with neighbors vertically
         for(int dy = -1; dy <= 1; dy += 2)
         {
            const BlockType type = start->GetType(x, y + dy);
            if( type == BLOCK_11 )
            {
               Node *neighbor = new Node(start);
               neighbor->Swap(x, y, 0, dy);
               AddNeighbor(neighbor, all_states, output);
            }
            else if( type == BLOCK_12 &&
                     start->Get(x, y + dy) == start->Get(x, y + dy * 2) )
            {
               Node *neighbor = new Node(start);
               neighbor->Swap(x, y, 0, dy * 2);
               AddNeighbor(neighbor, all_states, output);
            }
            else if( type == EMPTY )
            {
               if( start->GetType(x, y + dy * 2) == BLOCK_11 )
               {
                  Node *neighbor = new Node(start);
                  neighbor->Swap(x, y, 0, dy * 2);
                  AddNeighbor(neighbor, all_states, output);
               }
               else if( start->GetType(x, y + dy * 2) == BLOCK_12 &&
                        start->Get(x, y + dy * 2) == start->Get(x, y + dy * 3) )
               {
                  Node *neighbor = new Node(start);
                  neighbor->Swap(x, y, 0, dy * 2);
                  neighbor->Swap(x, y + dy, 0, dy * 2);
                  AddNeighbor(neighbor, all_states, output);
               }
            }
         }

         if( start->Get(x + 1, y) == kEmpty )
         {
            for(int dy = -1; dy <= 1; dy += 2)
            {
               // Swap 2x1 vertically
               if( start->GetType(x, y + dy) == BLOCK_21 &&
                   start->Get(x, y + dy) == start->Get(x + 1, y + dy) )
               {
                  Node *neighbor = new Node(start);
                  neighbor->Swap(x, y, 0, dy);
                  neighbor->Swap(x + 1, y, 0, dy);
                  AddNeighbor(neighbor, all_states, output);
               }

               // Swap 2x2 vertically
               if( start->GetType(x, y + dy) == BLOCK_22 &&
                   start->Get(x, y + dy) == start->Get(x + 1, y + dy) &&
                   start->Get(x, y + dy * 2) == start->Get(x + 1, y + dy * 2) &&
                   start->Get(x, y + dy) == start->Get(x, y + dy * 2) )
               {
                  Node *neighbor = new Node(start);
                  neighbor->Swap(x, y, 0, dy * 2);
                  neighbor->Swap(x + 1, y, 0, dy * 2);
                  AddNeighbor(neighbor, all_states, output);
               }

               // Swap 1x1 diagonally
               if( start->GetType(x, y + dy) == BLOCK_11 )
               {
                  Node *neighbor = new Node(start);
                  neighbor->Swap(x, y + dy, 1, -dy);
                  AddNeighbor(neighbor, all_states, output);
               }
               if( start->GetType(x + 1, y + dy) == BLOCK_11 )
               {
                  Node *neighbor = new Node(start);
                  neighbor->Swap(x + 1, y + dy, -1, -dy);
                  AddNeighbor(neighbor, all_states, output);
               }
            }
         }

         if( start->Get(x, y + 1) == kEmpty )
         {
            for(int dx = -1; dx <= 1; dx += 2)
            {
               // Swap 1x2 horizontally
               if( start->GetType(x + dx, y) == BLOCK_12 &&
                   start->Get(x + dx, y) == start->Get(x + dx, y + 1) )
               {
                  Node *neighbor = new Node(start);
                  neighbor->Swap(x, y, dx, 0);
                  neighbor->Swap(x, y + 1, dx, 0);
                  AddNeighbor(neighbor, all_states, output);
               }

               // Swap 2x2 horizontally
               if( start->GetType(x + dx, y) == BLOCK_22 &&
                   start->Get(x + dx, y) == start->Get(x + dx, y + 1) &&
                   start->Get(x + dx * 2, y) == start->Get(x + dx * 2, y + 1) &&
                   start->Get(x + dx, y) == start->Get(x + dx * 2, y) )
               {
                  Node *neighbor = new Node(start);
                  neighbor->Swap(x, y, dx * 2, 0);
                  neighbor->Swap(x, y + 1, dx * 2, 0);
                  AddNeighbor(neighbor, all_states, output);
               }

               // Swap 1x1 diagonally
               if( start->GetType(x + dx, y) == BLOCK_11 )
               {
                  Node *neighbor = new Node(start);
                  neighbor->Swap(x + dx, y, -dx, 1);
                  AddNeighbor(neighbor, all_states, output);
               }
               if( start->GetType(x + dx, y + 1) == BLOCK_11 )
               {
                  Node *neighbor = new Node(start);
                  neighbor->Swap(x + dx, y + 1, -dx, -1);
                  AddNeighbor(neighbor, all_states, output);
               }
            }
         }
      }
   }
}

// }}}

int main()
{
   Node *root = new Node(NULL);
   for(int y = 0; y < kHeight; y++)
      for(int x = 0; x < kWidth; x++)
         root->SetCell(x, y, kStart[y][x]);
   InitBlockTypes(*root);

   SeenNodes seen;
   seen.insert(root->GetFingerprint());
   NodeQueue queue, garbage;
   queue.push(root);
   while( !queue.empty() )
   {
      Node *node = queue.front();
      garbage.push(node);
      queue.pop();
      if( node->Goal() )
      {
         int moves;
         OutputSolution(*node, &moves);
         while( !queue.empty() )
         {
            delete queue.front();
            queue.pop();
         }
         break;
      }
      FindNeighbors(node, &seen, &queue);
   }

   // Garbage collect all parent nodes at the end.  We can't delete
   // them earlier because they might be referenced by multiple nodes
   // in the parent pointer.
   while( !garbage.empty() )
   {
      delete garbage.front();
      garbage.pop();
   }

   return 0;
}