#include <fstream.h>
#include <assert.h>
#include <stdlib.h>
#define MAXROWS 8
#define MAXCOLS 8
#define MAXLIMIT 40
#define DEBUGMODE false
#define MAXORIENT 10
#define MAXPIECE 6


int frows;
int fcols;
int limit;
int numsols[MAXLIMIT];

fstream ominoStream;

int wi=0;
int he=0;
int orient=0;
int wid[MAXORIENT];
int hei[MAXORIENT];
int pnt[MAXORIENT][MAXPIECE][MAXPIECE];

int grid[MAXROWS*MAXCOLS];
int check[(MAXROWS+2)*MAXCOLS];

void printpent(int ori) {
  for (int lcv2=0;lcv2<hei[ori];lcv2++) {
    for (int lcv3=0;lcv3<wid[ori];lcv3++) 
      cout << ((pnt[ori][lcv2][lcv3]==1) ? 'X' : 'O');
    cout << "\n";
  }
}

void printpiece() {
  cout << "orient " << orient << "\n";
  cout << "he " << he << "\n";
  cout << "wi " << wi << "\n";
  cout << "S\n";
  for (int lcv1=0;lcv1<orient;lcv1++) {
    printpent(lcv1);
    cout << "\n";
  }
}

void getomino(void) {
  // load wi, he, orient, wid, hei, pnt, etc.
  char temp;
  int myhe,mywi;

  for (int lcv=0;lcv<MAXORIENT;lcv++) {
    wid[lcv]=0;
    hei[lcv]=0;
  }
  wi=0;
  he=0;

  while (ominoStream.peek() != 'S') ominoStream.get();
  ominoStream.get();  // 'S'
  ominoStream.get();  // '\n'
  orient = 0;
  while (ominoStream.peek() != EOF) {
    while (ominoStream.peek() == '\n') ominoStream.get();
    myhe=0;
    while (ominoStream.peek() != '\n') {
      mywi=0;
      while (ominoStream.peek() != '\n') {
        temp = ominoStream.get();
if (DEBUGMODE) cerr << "read " << temp 
  << " into pnt[" << orient << "][" << myhe << "][" 
  << mywi << "]\n";
        pnt[orient][myhe][mywi] = (temp == 'X') ? 1 : 0 ;
        mywi++;
      }
      // finished getting the line, on to next line.
      if ((temp == 'X') && (wid[orient] < mywi)) wid[orient] = mywi;
      myhe++;
      ominoStream.get();  // get rid of /n.
    }
    // finished getting the piece, on to next piece.
    if (hei[orient] < myhe) hei[orient] = myhe;
    ominoStream.get(); // get rid of extra /n.

    if (wi < wid[orient]) wi = wid[orient];
    if (he < hei[orient]) he = hei[orient];
    orient++;
  }
  // if (DEBUGMODE) printpiece();
}

void print(int pieces) {
  int r,c;
  cout << pieces << " ominoes placed.\n";
  for (r=0;r<frows;r++) {
    for (c=0;c<fcols;c++) {
      cout << " " << grid[r*fcols+c];
    }
    cout << "\n";
  }
  cout << "\n";
}

bool checkslide(int n) {
  bool lblock=false;
  bool rblock=false;
  bool ublock=false;
  bool dblock=false;
  int loc;
  for (loc=0;loc<frows*fcols;loc++) if (grid[loc]==n) {
    if (!lblock) {
      if (loc%fcols==0) lblock=true;
      else if ((grid[loc-1] != 0) && (grid[loc-1] != n)) lblock=true;
    }
    if (!rblock) {
      if (loc%fcols==fcols-1) rblock=true;
      else if ((grid[loc+1] != 0) && (grid[loc+1] != n)) rblock=true;
    }
    if (!ublock) {
      if (loc/fcols==0) ublock=true;
      else if ((grid[loc-fcols] != 0) && (grid[loc-fcols] != n)) ublock=true;
    }
    if (!dblock) {
      if (loc/fcols==frows-1) dblock=true;
      else if ((grid[loc+fcols] != 0) && (grid[loc+fcols] != n)) dblock=true;
    }
  }
  return (lblock && rblock && ublock && dblock);
}

bool place(int n,int curloc,int ori) {
  int mypnt[MAXPIECE][MAXPIECE];
  int mywid,myhei;
  int r,c,currow,curcol;
  bool success = true;
  mywid = wid[ori];
  myhei = hei[ori];
  mypnt = pnt[ori];
  currow = curloc/fcols;
  curcol = curloc%fcols;
  // see if we can place
  for (r=0;r<myhei;r++) for (c=0;c<mywid;c++) if (mypnt[r][c]==1) {
    if (currow+r >= frows) success = false; 
    else if (curcol+c >= fcols) success = false; 
    else if (grid[(currow+r)*fcols+curcol+c] != 0) success = false; 
  }
  if (success) {
if (DEBUGMODE) printpent(ori);
if (DEBUGMODE) cerr << mypnt[0][0] << mypnt[0][1] << "\n";
if (DEBUGMODE) cerr << mypnt[1][0] << mypnt[1][1] << "\n";
if (DEBUGMODE) cerr << mypnt[2][0] << mypnt[2][1] << "\n";
    for (r=0;r<myhei;r++) for (c=0;c<mywid;c++) if (mypnt[r][c]==1) {
      grid[(currow+r)*fcols+curcol+c] = n;
if (DEBUGMODE) cerr << "myhei is " << myhei << 
   " and mywid is " << mywid << "\n";
if (DEBUGMODE) cerr << "Placed " << n << " at " << (currow+r)*fcols
 + curcol + c << " which is (" << currow + r << "," << curcol + c << ")\n";
    }
    int checkpoint = (currow+myhei)*fcols+curcol+mywid;
    while (check[checkpoint]!=0) checkpoint++;
    check[checkpoint]=n;
  }
  return(success);
}

int unplace(int n,int curloc,int ori) {
  for (int a=0;a<frows*fcols;a++) 
    if (grid[a]==n) grid[a]=0;
  for (int a=0;a<(frows+2)*fcols;a++) 
    if (check[a]==n) check[a]=0;
}

void recurse(int n, int curloc) {
  // put the nth omino at location curloc.  Or not.
  if (n-1>limit) return;

  if (curloc == (frows+2)*fcols) {
    (numsols[n-1])++;
    print(n-1);
  } else if (curloc >= frows*fcols) {
    if ((check[curloc] == 0) || (checkslide(check[curloc]))) {
      recurse(n,curloc+1);
    }
  } else {
    if (DEBUGMODE) { cout << "Checking " << check[curloc] << " at "
        << curloc << "...\n"; }
    if ((check[curloc] == 0) || (checkslide(check[curloc]))) {
      for (int ori=0;ori<orient;ori++) {
        if (place(n,curloc,ori)) {
          if (DEBUGMODE) { cout << "Placing " << n <<
                 " with orientation " << ori << "...\n"; }
          if (DEBUGMODE) { print(0); }
          recurse(n+1,curloc+1);
          unplace(n,curloc,ori);
        }
      }
      recurse(n,curloc+1);
    }
  }
}

void main(int argc, char * argv []) {
  frows = atoi(argv[1]);
  fcols = atoi(argv[2]);
  limit = atoi(argv[3]);
  ominoStream.open(argv[4],ios::in);
  assert(!ominoStream.fail());
  getomino();
  ominoStream.close();
  int curloc=0;
  int r;
  for (r=0;r<MAXLIMIT;r++) numsols[r]=0;
  for (r=0;r<frows*fcols;r++) grid[r]=0;
  for (r=0;r<frows*fcols;r++) check[r]=0;
  recurse(1,curloc);
  cout << "Done with \"" << argv[4] << "\" \n";
  for (r=0;r<=limit;r++) 
    cout << numsols[r] << " solutions found for " << r << " pieces.\n";
}