// chomp: alleen bepalen winnende zet
// geen klasse structuur om het simpel te houden
// ook eenvoudig interface,
// dus geen uitvoerige tests of de invoer wel uit
// een getal bestaat, bijvoorbeeld

#include <iostream>
#include <stdlib.h>
#include <cstdlib>
#include <ctime>
using namespace std;

const int Mmax = 8, Nmax = 9;
// reep niet al te groot nemen
const int Max = 100000000;

bool reep[Mmax][Nmax];
// true betekent dat een plek nog deel van de reep is; 
// false betekent dat het stukje chocola op die plek al opgegeten is

int opslag[Max];
// voor het DP-gedeelte
   
   
void init ( bool reep[Mmax][Nmax], int m, int n ){
int i,j;
   for (i=0; i<Mmax;i++)
       for (j=0; j<Nmax; j++)
           reep[i][j] = false;
   for (i=0; i<m;i++)
       for (j=0; j<n; j++)
           reep[i][j] = true;
} // init


void inlezen (int & m, int & n){
// afmetingen van de reep inlezen
   cout << "Geef het aantal rijen m, niet groter dan " << Mmax << " ......";
   cout << endl; 
   cin >> m;
   if ((m<1) ||(m>Mmax)){
     cout << "m te groot of te klein " << endl;
     exit (1);
   }   
   cout << "Geef het aantal kolommen n, niet groter dan " << Nmax << " ......";
   cout << endl; 
   cin >> n;
   if ((n<1) ||(n>Nmax)){
     cout << "n te groot of te klein " << endl;
     exit (1);
   }   
} // inlezen


void drukaf (bool reep[Mmax][Nmax], int m, int n ){
int i, j;
     for (i=0; i<m;i++){
        for (j=0; j<n; j++){
	   if ((i == 0) && (j == 0) && reep[i][j])
	      cout << '#' << "  ";
	   else { // niet vergiftigde stukjes
	      if ( reep[i][j] )
	         cout << 'X' << "  ";
	      else 
	         cout << ' ' << "  "; 
	   } 
        } // for j
	cout << endl;
     } // for i
} // drukaf

void nieuwereep (int & m, int & n){
   inlezen(m, n);
   init(reep, m, n);
   drukaf(reep,m,n);
}


void copieer(bool reep[Mmax][Nmax], bool hulp[Mmax][Nmax]){
   int i,j;
   for (i=0; i<Mmax;i++)
      for (j=0; j<Nmax; j++)
         hulp[i][j] = reep[i][j];
} // copieer


void doezet(bool reep[Mmax][Nmax], int i, int j, int m, int n){
// voert de hap vanuit (i,j) uit
    int k,l;
    for (k = i; k < m; k++)
       for (l=j; l<n; l++)
       	  reep[k][l] = false;
} // doezet


int blokjes (bool rooster[Mmax][Nmax], int m, int n){
// telt het aantal blokjes
   int i, j;
   int teller = 0;
   for (i=0; i<m; i++)
     for (j=0; j<n; j++)
        if (rooster[i][j])
	   teller++;
   return teller;
} // blokjes


bool allesop(bool rooster[Mmax][Nmax], int m, int n){
   if (blokjes(rooster,m,n) > 0)
      return false;
   else
      return true;
} // allesop    


//*******************************************
// recursieve functie

bool winstzet (bool rooster[Mmax][Nmax], int m, int n, int & rij, int & kolom ){
   
   bool kopie[Mmax][Nmax];
   int k,l;
   
   if (allesop(rooster, m, n))
      return true; // tegenstander heeft giftige stukje gegeten
   else{
      for (k=0; k<m;k++){
         for (l=0; l<n; l++){
	      
	    if (rooster[k][l]){
	       copieer(rooster, kopie);
               doezet(kopie,k,l,m,n);
	       rij = -1; kolom = -1;
	       
	       if (!winstzet(kopie,m,n,rij,kolom)){
	       // als de vervolgstand niet (!) winnend is voor je tegenstander
	       // is deze dus wel winnend voor jou: winnende zet
	       // zodra een winnende zet gevonden --> deze retourneren
		  rij = k; kolom = l;
	   	  return true;
	       }
	       
	    } // if rooster
	 } // for l  
      } // for k
      return false;
   } // else 
   	   
} // winstzet

//*********************************************************************

//*********************************************************************
// functies nodig voor de DP-oplossing: Dynamisch programmeren
// In dit geval recursie met een array waarin (gecodeerd) de beste zet voor
// elke stand wordt/staat opgeslagen


void vul (int slaop[Max]){
// vult array slaop initieel met -1 (uitslag nog onbekend)
   for (int i = 0; i<Max; i++)
      slaop[i] = -1;   
} // vul


int codeer( bool rooster[Mmax][Nmax], int m, int n ) {
   int rij, kolom, teller, code; 
   code = 0;
   for (rij = m-1;rij>=0;rij--){
      teller = 0;
      for (kolom = 0; kolom<n; kolom++)
         if ( rooster[rij][kolom] )
	    teller++;
      // teller geeft nu het aantal blokjes in rij rij
      code = code*10+teller;
   }
   return code;
} // codeer


//******************************************************
// recursieve functie met array: dynamisch programmeren

bool DPwinstzet (bool rooster[Mmax][Nmax], int m, int n, int & rij, int & kolom ){
// opslagarray is globaal; aanroep met rij=kolom=-1
// array-element -1: nooit bekeken; -2: verliezend;

   bool kopie[Mmax][Nmax];
   int k,l, hulp;
   
   int plaats = codeer(rooster,m,n);
   
   hulp = opslag[plaats];
   if ( (hulp != -1) ){  // al bekend
      if (hulp == -2) // verloren
         return false;
      else {  // winnend dus
         kolom = hulp%10;
         rij = hulp/10;
         return true;
      } // else
   } // if
   
   else // nog niet bekend
   {
     if (allesop(rooster, m, n)) {
        // lege reep heeft geen winnende zet, dus niet opslaan.
        return true; // tegenstander heeft giftige stukje gegeten
     }	
     else{ 
     // er zijn nog stukjes reep over
        for (k=0; k<m;k++){
           for (l=0; l<n; l++){
	      if (rooster[k][l]){
	         copieer(rooster, kopie);
                 doezet(kopie,k,l,m,n);
		 rij = -1; kolom = -1;
		 
	         if (!DPwinstzet(kopie,m,n,rij,kolom)){
		 // als de vervolgstand niet (!) winnend is voor je tegenstander
	         // is deze dus wel winnend voor jou: winnende zet
	         // zodra een winnende zet gevonden --> deze opslaan en retourneren
		    rij = k; kolom = l;
		    opslag[plaats]=rij*10+kolom;
	   	    return true;
	         } //if 
		 
	       } // if rooster
	    } //for l  
         } // for k
          
	 // alle zetten afgelopen; blijkbaar geen winnende zet gevonden
         opslag[plaats]=-2;
         return false;
	
      } // nog stukjes over
   } // nog niet bekend
  	   
} // DPwinstzet


//*********************************************************************

//*********************************************************************
// functies nodig / gebruikt om chomp te spelen
// hier gebruiken we de DP-methode (recursie+array) om winnende zet te vinden



void chompspelen (bool rooster[Mmax][Nmax], int m, int n){

   bool winnen;
   int rij, kolom;
       
   while (!(allesop(rooster, m, n))) {
   
      rij = -1; kolom = -1;
      vul(opslag); 
      winnen = DPwinstzet(rooster,m,n,rij,kolom);
      
      // winnende hap wordt berekend
      if (winnen){
         cout << "Winnende zet: " << "rij " << rij+1 << ", kolom " << kolom+1 << endl;
         cout << endl;
      }
      else
         cout << "Stand niet winnend " << endl;
	 
      // gebruiker neemt een hap
      cout << "Welke hap wil je nemen? Geef de rij <enter>" << endl;
      cin >> rij;
      cout << "Geef de kolom <enter>" << endl;
      cin >> kolom;
      if ((rij < 1) || (rij > Mmax) || (kolom < 1) || (kolom > Nmax) || (!rooster[rij-1][kolom-1])){
	 cout << "Niet bestaande rij/kolom ingevoerd of blokje bestaat niet meer." << endl;
	 cout << "Helemaal opnieuw beginnen. Sorry" << endl;
	 exit(1);
      } 
      rij = rij -1; kolom = kolom - 1;
      // vanwege C++: arrays lopen van 0 tot max-1 i.p.v. van 1 tot max
      doezet(rooster,rij,kolom,m,n);
      drukaf(rooster,m,n);
      cout << endl;
      
      if (allesop(rooster, m, n))
         cout << " Je hebt verloren ! " << endl;
      else {
      // domme, randomzet van de computer;
         cout<< "Nu gaat de computer happen." << endl;
	 if (blokjes(rooster,m,n) > 1){
            rij = rand( )%Mmax;
	    kolom = rand( )%Nmax;
	    while (!rooster[rij][kolom] || ((rij == 0) && (kolom == 0))){
	    // happen bij een bestaand blokje, maar niet het vergiftigde
	       rij = rand( )%Mmax;
	       kolom = rand( )%Nmax;
	    } 
	 }
	 else {
	 // nog maar 1 zet mogelijk
	    rij = 0;
	    kolom = 0;
	 }
	   
	 doezet(rooster,rij,kolom,m,n);
	 
	 if (allesop(rooster, m, n)) {
	    cout << " Je hebt gewonnen ! " << endl; 
	    cout << " De computer heeft het vergiftigde stukje gegeten" << endl;
	 }   
    	 else {
	    drukaf(rooster,m,n);
	    cout << endl;
	 }
      } // else: randomzet 
   } // while 
   
}  // chompspelen



   

//********************************************************
// Hoofdprogramma

int main (){

// chomp met recursie en met of zonder hulparray (opslag)
// **************************************************************

   int m, n; // afmetingen van de reep
   int row = -1, kol = -1; // winnende zet
   char keuze = '5';
   srand ((unsigned)time(0));
   // randomgenerator aanzetten voor random zetten tegen computer
   bool winnend;
   // omdat winstzet en DPwinstzet een boolean opleveren

   while ( !(keuze == '4') ) {

      cout << " maak je keuze <enter> " << endl;
      cout << " 1:  berekenen winnende zet voor chomp ZONDER array" << endl;
      cout << " 2:  berekenen winnende zet voor chomp MET array" << endl;
      cout << " 3:  spelen van chomp" << endl;
      cout << " 4:  stoppen" << endl;
      cin >> keuze;
    
      switch (keuze) {
         case '1': nieuwereep(m,n);
                   winnend = winstzet(reep, m,n,row,kol);
	           cout << endl;
                   cout << "Winnende zet: " << "rij " << row+1 << ", kolom " << kol+1;
                   cout << endl;
                   break;
         case '2': nieuwereep(m,n);
                   vul(opslag); 
                   winnend = DPwinstzet(reep, m,n,row,kol);
	           cout << endl;
                   cout << "Winnende zet met DP: " << "rij " << row+1 << ", kolom " << kol+1;
                   cout << endl;
	           break;
         case '3': nieuwereep(m,n);
                   chompspelen(reep,m,n);
                   break;
	 case '4': exit(1);
         default :  cout << "Niet toegestane keuze "<< endl;
      }
	
   } // while

  return 0;
}