string g_pic[] = {
   "..........",
   "...#####..",
   "..#....#..",
   "..####.#..",
   "..#....#..",
   "..........",
   "..##..#...",
   "..#.#.#...",
   "..#..##...",
   "..........",
   "......#..#",
   "...####.#.",
   "...#..##..",
   "...####..." };

struct Plate { int sx, sy, cost; };
Plate plates[] = { { 1, 1, 1000 }, { 1, 2, 150 }, { 2, 1, 150 }, { 1, 3, 250 }, { 3, 1, 250 }, { 3, 3, 1 } };

int SY = sizeof(g_pic)/sizeof(g_pic[0]);
int SX = g_pic[0].length();
const int MAXSIZE = 64;
const int NUMPLATES = sizeof(plates)/sizeof(plates[0]);
__int64 zobristHash[MAXSIZE][MAXSIZE] = { 0 };
__int64 zobristPlateHash[NUMPLATES][MAXSIZE][MAXSIZE] = { 0 };

__int64 rand64() { return ((__int64)rand()<<0)^((__int64)rand()<<15)^((__int64)rand()<<30)^((__int64)rand()<<45)^((__int64)rand()<<60); }

bool findNextEmpty( int& x, int& y )
{
   while ( 1 )
   {
      if ( g_pic[y][x] == '.' ) return true;
      x++;
      if ( x >= SX ) { x = 0; y++; }
      if ( y >= SY ) return false;
   }
}

map<__int64, int> bestCost;
int findCost( int posx, int posy, __int64 hash )
{
   if ( bestCost.count( hash ) )
      return bestCost[hash];

   if ( !findNextEmpty( posx, posy ) ) return bestCost[hash] = 0; // done -- no empty spots left

   int ret = INT_MAX;

   // try to place each kind of plate with upper-left corner at posx, posy
   for ( int plateIdx = 0; plateIdx < NUMPLATES; plateIdx++ ) if ( zobristPlateHash[plateIdx][posy][posx] != 0 )
   {
      bool isLegalToPlace = true;
      for ( int y = 0; y < plates[plateIdx].sy; y++ )
      for ( int x = 0; x < plates[plateIdx].sx; x++ )
         if ( g_pic[posy+y][posx+x] != '.' ) { isLegalToPlace = false; y=999; break; }
      if ( !isLegalToPlace ) continue;

      // if we already know the cost to fill the remainder of the picture:
      if ( bestCost.count( hash ^ zobristPlateHash[plateIdx][posy][posx] ) )
      {
         int cost = plates[plateIdx].cost + bestCost[hash ^ zobristPlateHash[plateIdx][posy][posx]];
         ret = min( ret, cost );
         continue;
      }

      // place the piece
      for ( int y = 0; y < plates[plateIdx].sy; y++ )
      for ( int x = 0; x < plates[plateIdx].sx; x++ )
         g_pic[posy+y][posx+x] = '#';

      // cost = cost of this piece + optimal cost of filling the rest
      int cost = plates[plateIdx].cost + findCost( posx, posy, hash ^ zobristPlateHash[plateIdx][posy][posx] );
      ret = min( ret, cost );

      // un-place the piece
      for ( int y = 0; y < plates[plateIdx].sy; y++ )
      for ( int x = 0; x < plates[plateIdx].sx; x++ )
         g_pic[posy+y][posx+x] = '.';
   }

   // memoize
   return bestCost[hash] = ret;
}

void reconstructSolution( int posx, int posy, __int64 hash, int expectedCost )
{
   if ( !findNextEmpty( posx, posy ) ) return; // done

   for ( int plateIdx = 0; plateIdx < NUMPLATES; plateIdx++ ) if ( zobristPlateHash[plateIdx][posy][posx] != 0 )
   {
      bool ok = true;
      for ( int y = 0; y < plates[plateIdx].sy; y++ )
      for ( int x = 0; x < plates[plateIdx].sx; x++ )
         if ( g_pic[posy+y][posx+x] != '.' )
            ok = false;
      if ( !ok ) continue;

      int cost = plates[plateIdx].cost + findCost( posx, posy, hash ^ zobristPlateHash[plateIdx][posy][posx] );
      if ( cost != expectedCost ) continue;

      for ( int y = 0; y < plates[plateIdx].sy; y++ )
      for ( int x = 0; x < plates[plateIdx].sx; x++ )
         g_pic[posy+y][posx+x] = '0' + plateIdx;
      reconstructSolution( posx, posy, hash ^ zobristPlateHash[plateIdx][posy][posx], expectedCost - plates[plateIdx].cost );
      break;
   }
}

void main()
{
   // assign random zobrist hash value to each single square
   for ( int posy = 0; posy < SY; posy++ )
   for ( int posx = 0; posx < SX; posx++ )
      zobristHash[posy][posx] = rand64();

   // the hash values of multiple squares is just each single square XOR'ed together
   // pre-calculate the hash value for each piece at each position
   for ( int plateIdx = 0; plateIdx < NUMPLATES; plateIdx++ )
   for ( int posy = 0; posy <= SY - plates[plateIdx].sy; posy++ )
   for ( int posx = 0; posx <= SX - plates[plateIdx].sx; posx++ )
   {
      for ( int y = 0; y < plates[plateIdx].sy; y++ )
      for ( int x = 0; x < plates[plateIdx].sx; x++ )
         zobristPlateHash[plateIdx][posy][posx] ^= zobristHash[posy+y][posx+x];
   }

   int cost = findCost( 0, 0, 0 );
   echoprintf( "lowest cost = %d\n", cost );
   echoprintf( "(hashmap size = %d)\n", bestCost.size() );

   reconstructSolution( 0, 0, 0, cost );
   echoprintf( "\n" );
   for ( int y = 0; y < SY; y++ )
      echoprintf( "%s\n", g_pic[y].c_str() );
   echoprintf( "\n" );
}

// output:
//
//lowest cost = 7352
//(hashmap size = 41936)
//
//1112222221
//111#####11
//11#2222#13
//11####1#13
//22#1221#13
//1221122555
//11##11#555
//11#1#1#555
//11#11##221
//1122112211
//122221#11#
//555####1#0
//555#22##22
//555####444