/* FILE: randLessieField.cpp   last change: 20-Aug-2012   author: Romeo Rizzi
 * This program generates a random lessie field as for execise "lessie" of the 3-Sept-2012 exam in Algorithms.
 * Usage syntax:
 *   > randLessieField out_file m n nL nH seed
 *                             (m=righe, colonne, num Lessie's positions, num Home's positions, random seed generator)
 */

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

const int MAX_M = 1000;
const int MAX_N = 1000;
int m, n, nL, nH;
bool wall[MAX_M+2][MAX_N+2];
bool lessie[MAX_M+2][MAX_N+2];
bool home[MAX_M+2][MAX_N+2];

int RandNumber(int min, int max) {
  /* returns an integer in [min, max]
   * see Stroustrup "The c++ Programming Language" 3th edition pg. 685
   * for comments on the following manipulation choice.
   * In particular, considerations on the bad quality of low bits come into account.
   */
 return min + (int) ( (max-min) * (double(rand()) / RAND_MAX) );
}

void skip(int &i, int &j) {
  j++;
  if(j > n) { j = 1; i++; }
  if(i > m) { i = 1; }
}

template <class genType>
void displayMatrix(genType mat[MAX_M+2][MAX_N+2]) {
  for(int i = 1; i <= m; i++) {
    for(int j = 1; j <= n; j++)
      cout << mat[i][j] << " ";
    cout << endl;
  }  cout << endl;
}

int main(int argc, char** argv) {
  srand(time(NULL));
  m = atoi(argv[2]);
  n = atoi(argv[3]);
  nL = 1; nH = 1;
  if(argc > 4) nL = atoi(argv[4]);
  if(argc > 5) nH = atoi(argv[5]);
  if(argc > 6) srand( atoi(argv[6]) );

  assert( nL < m*n); assert( nH < m*n);

  for(int i = 0; i <= m +1; i++)
    for(int j = 0; j <= n +1; j++)  wall[i][j] = lessie[i][j] = home[i][j] = false;

  for(int count = 1; count <= nL; count++) {
    int i = RandNumber(1, m); int j = RandNumber(1, n);
    while ( lessie[i][j] )  skip(i,j);
    lessie[i][j] = true;
  }

  for(int count = 1; count <= nH; count++) {
    int i = RandNumber(1, m); int j = RandNumber(1, n);
    while ( home[i][j] )  skip(i,j);
    home[i][j] = true;
  }
  // displayMatrix(wall); displayMatrix(lessie); displayMatrix(home); 

  for(int i = 1; i <= m; i++)
    for(int j = 1; j <= n; j++)
      if( (!lessie[i][j]) & (!home[i][j]) & (RandNumber(1, 5 + max(0, m*n -nH -nL) /1000 ) == 5)
        ) wall[i][j] = true;
 
  int i = 1; int j = 1; wall[1][1] = false; // displayMatrix(wall);
  while( (i<m) & (j<n) ) {
    if( (wall[i+1][j]) & (wall[i][j+1]) ) {
         if(RandNumber(1,2) == 1) wall[i+1][j] = false;
         else wall[i][j+1] = false;
    }
    if( (i<m) & (!wall[i+1][j]) ) i++;
    if( (j<n) & (!wall[i][j+1]) ) j++;
    // cout << "i = " << i << ", j = " << j << endl; displayMatrix(wall);
  }
  while( i < m ) wall[++i][j] = false;
  while( j < n ) wall[i][++j] = false;

  ofstream fout(argv[1]);  // displayMatrix(wall);
  fout << m << " " << n << " "  << nL << " " << nH << " " << endl;
  for(int i = 1; i <= m; i++) {
    for(int j = 1; j <= n; j++)
      fout <<  wall[i][j] << " ";
    fout << endl;
  }
  for(int i = 1; i <= m; i++)
    for(int j = 1; j <= n; j++)
      if( lessie[i][j] ) fout << i << " "  << j << endl;
  for(int i = 1; i <= m; i++)
    for(int j = 1; j <= n; j++)
      if( home[i][j] ) fout << i << " "  << j << endl;
  fout.close();
  return 0;
}