#include <iostream>
using namespace std;

const int m=20; // maximaal speelveld horizontaal
const int n=20; // en verticaal

// een leeg console scherm
void leegscherm ( ) {
  int i;
   for (i=0;i<30;i++)
     cout << endl;
} // leegscherm

long randomgetal ( ) {
  static long getal=42;
  getal=(221*getal+1)%100;
  return getal;
} // randomgetal

// plek op het bord 
class vakje {
  public:
    vakje* volgende;
    int rij;
    int kolom;
}; // vakje

// de klasse met hierin het bord en de meeste functies
class bord {
  public:
    vakje* eerste;
    vakje* laatste;
    int x; // grote van het bord horizontaal
    int y; // en verticaal
    int A[m][n];
    int beurt; // wie aan de beurt is, 0=zwart, 1=wit
    int maxdiepte; // hoever slimme zet moet vooruit denken
    bord (int, int, int);
    void zeterachter (int, int);
    void veranderkleur ( );
    void verwijder ( );    
    void maakleeg ( );
    void drukaf ( );
    bool toegestanezet (int, int);
    void doezet (int, int);
    bool zetmogelijk ( );
    void randomzet (int&, int&);
    int stand ( );
    void winnaar ( );
    void slimmezet (int&, int&);
    int slimzet (int, int&, int&);
    void copy (int B[ ][n]);
    int eval ( );
  private:
}; // bord

// zet een coordinaat in de rij met vakjes die verandert moeten worden
void bord::zeterachter (int p, int q) {
  vakje* w=new vakje;
  w->rij=p;
  w->kolom=q;
  w->volgende=NULL;
  if (laatste!=NULL)
    laatste->volgende=w;
  laatste=w;
  if (eerste==NULL)
    eerste=w;
} // bord::zeterachter

// verwijder de rij met vakjes die verandert moeten worden
void bord::verwijder ( ) {
  vakje* hulp=eerste;
  while (hulp!=NULL) {
    eerste=eerste->volgende;
    delete hulp;
    hulp=eerste;
  } // while
  laatste=NULL;
} // bord::verwijder

// verander de kleur van het bord aan de hand van de rij
void bord::veranderkleur ( ) {
  int i;
  int j;
  vakje* hulp=eerste;
  while (hulp!=NULL) {
    i=hulp->rij;
    j=hulp->kolom;
    A[j][i]=beurt+1;
    hulp=hulp->volgende;
  } // while
} // bord::veranderkleur
  
// de constructor
bord::bord (int i, int j, int k) {
  x=i;
  y=j;
  maxdiepte=k;
  maakleeg ( );
  A[y/2][x/2]=2;
  A[y/2-1][x/2-1]=2;
  A[y/2][x/2-1]=1;
  A[y/2-1][x/2]=1;
} // bord::bord

// vul de hele array met nullen
void bord::maakleeg ( ) {
  int i;
  int j;
  for (i=0;i<y;i++)
    for (j=0;j<x;j++)
      A[i][j]=0;
} // bord::maakleeg

// druk het bord met coordinaten af
void bord::drukaf ( ) {
  int i;
  int j;
  bool xgroot = false;
  bool ygroot = false;
  if(x > 9)
   xgroot = true;
  if(y > 9)
   ygroot = true;
  cout << "  ";
  if(xgroot)
    cout << " ";
  for (j=0;j<x;j++) {
    cout << j+1 << " ";
    if(xgroot && j < 9)
      cout << " ";
  }
  cout << endl;
  for (i=0;i<y;i++) {
    cout << i+1 << " ";
    if(ygroot && i < 9)
      cout << " ";
    for (j=0;j<x;j++) {
      if (A[i][j]==0)
        cout << ". ";
      else if (A[i][j]==1) 
        cout << "Z ";
      else if (A[i][j]==2)
        cout << "W ";
      if(xgroot)
        cout << " ";
    } // for
    cout << endl;
  } // for
} // bord::drukaf  

// controleer of een zet is toegestaan
bool bord::toegestanezet (int p, int q) {
  int Z[16]={0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1};
  int v=0; // kiezen 2 getallen uit array
  int w=1;
  int i; // richting coordinaten
  int j;
  if (A[q][p]==0) {
    while (v!=16) {
      i=Z[v];
      j=Z[w];
      if (A[q+j][p+i]==((beurt+1)%2)+1 && p+i>=0 && q+j>=0 && p+i<y &&
      q+j<x) {
        while (A[q+j][p+i]!=0 && A[q+j][p+i]!=beurt+1 && p+i>=0 && q+j>=0 && p+i<y &&
        q+j<x) {
 	  i=i+Z[v];
	  j=j+Z[w];
	  if (A[q+j][p+i]==beurt+1)
            return true;
	} // while
      } // if  
      v=v+2;
      w=w+2;
    } // while
  } // if
  return false;
} // bord::toegestanezet

// doe de zet en zet alle coordinaten die verandert moeten worden op een stapel
void bord::doezet (int p, int q) {
  int Z[16]={0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1};
  int v=0; // kiezen 2 getallen uit array
  int w=1;
  int i; // richting coordinaten
  int j;
  eerste=NULL;
  laatste=NULL;
  if (A[q][p]==0) {
    while (v!=16) {
      i=Z[v];
      j=Z[w];
      if (A[q+j][p+i]==((beurt+1)%2)+1 && p+i>=0 && q+j>=0 && p+i<y &&
      q+j<x) {
        while (A[q+j][p+i]!=0 && A[q+j][p+i]!=beurt+1 && p+i>=0 && q+j>=0 && p+i<y &&
        q+j<x) {
	  zeterachter (p+i, q+j);
 	  i=i+Z[v];
	  j=j+Z[w];
	} // while
	if (A[q+j][p+i]==0 || p+i<0 || q+j<0 || p+i>=y || q+j>=x)
	  verwijder ( );
	else {
	  zeterachter (p, q);
	  veranderkleur ( );
	  verwijder ( );
	} // else   
      } // if  
      v=v+2;
      w=w+2;
    } // while
  } // if
} // bord::doezet

// kijk of er nog een zet mogelijk is
bool bord::zetmogelijk ( ) {
  int i;
  int j;
  for (i=0;i<y;i++)
    for (j=0;j<x;j++)  
      if (toegestanezet (j, i))
        return true;
  return false;
} // bord::zetmogelijk

// de computer doet een willekeurige toegestane zet
void bord::randomzet (int& p, int& q) {
  int teller=0;
  int i;
  int j;
  vakje* hulp;
  for (i=0;i<y;i++)
    for (j=0;j<x;j++)
      if (toegestanezet (i, j)) {
        zeterachter (i, j);
        teller++;
      } // if
  hulp=eerste;
  j=randomgetal ( )%teller;
  for (i=0;i<j;i++)
    hulp=hulp->volgende;
  p=(hulp->rij+1);
  q=(hulp->kolom+1);
  verwijder ( );
} // bord::randomzet

// geef de stand terug
int bord::stand ( ) {
  int tellerzwart=0;
  int tellerwit=0;
  int i;
  int j;
  for (i=0;i<y;i++)
    for (j=0;j<x;j++) {
      if (A[i][j]==1)
        tellerzwart++;
      else if (A[i][j]==2)
        tellerwit++;
    } // for
  if (tellerzwart==tellerwit)
    return 0;
  else if (tellerzwart>tellerwit)
    return 1;
  else
    return 2;
} // bord::stand

// druk af wie de winnaar is geworden
void bord::winnaar ( ) {
  cout << endl << endl;
  if (stand ( )==2)
    cout << " De winnaar is: WIT!" << endl << endl;
  else if (stand ( )==1)
    cout << " De winnaar is: ZWART!" << endl << endl;
  else
    cout << "Het spel is gelijk geeindigd." << endl << endl;
} // bord::winnaar

// laat de computer een slimme zet doen
void bord::slimmezet (int & p, int & q) {
  slimzet (0, p, q);
  p++;
  q++;
} // bord::slimmezet

// de echte recursieve slimme zet
int bord::slimzet (int z, int & p, int & q) {
  int i;
  int j;
  int stand;
  int bestestand = 0;
  bool gevuld = false;   
  z++;
  if (zetmogelijk ( ) && z<maxdiepte) {
    bord tussen (x, y, maxdiepte);
    for (i=0;i<y;i++)
      for (j=0;j<x;j++) {
	    if (toegestanezet (i, j)) {
	      tussen.copy (A);
	      tussen.beurt=beurt; 
	      tussen.doezet (i, j);
	      tussen.beurt=(beurt+1)%2;
	      stand = tussen.slimzet (z, p, q);
	      if(beurt == 0) {
	        if(stand <= bestestand || !gevuld) {
	      	  bestestand = stand;
		  if(z == 1) {
	      	    p = i;
	      	    q = j;
		  } // if
		  gevuld = true;
	      	} // if
	      } // if
	      else if(beurt == 1) {
	        if(stand >= bestestand || !gevuld) {
	      	  bestestand = stand;
		  if(z == 1) {
	      	    p = i;
	      	    q = j;
		  } // if
		  gevuld = true;
	      	} // if
	      } // if
	    } // if
	  } // for
  } // if
  else {
  	bestestand = eval ( );
  }
  return bestestand;
} // bord::slimzet
  
// kopier array B in het bord
void bord::copy (int B [ ][n]) {
    int i;
    int j;
      for (i=0;i<y;i++)
        for (j=0;j<x;j++)
          A[i][j]=B[i][j];
} // bord::copy

// evalueer het bord en geef de waarde terug
int bord::eval ( ) {
  int tellerzwart=0;
  int tellerwit=0;
  int i;
  int j;
  for (i=0;i<y;i++)
    for (j=0;j<x;j++) {
      if (A[i][j]==1)
        tellerzwart++;
      else if (A[i][j]==2)
        tellerwit++;
    } // for
  return tellerwit - tellerzwart; 
} // bord::eval

// de klasse met borden om een zet terug te doen
class oudbord {
  public:
    oudbord* vorige;
    int C[m][n];
}; // oudbord

// de stapel van oude borden
class stapel {
  public:
    oudbord* eerste;
    oudbord* laatste;
    void zetopstapel (int A[ ][n], int, int);
    void haalvanstapel (int A[ ][n], int, int);
    void verwijderstapel ( );
}; // stapel

// zet een bord op de stapel
void stapel::zetopstapel (int A[ ][n], int x, int y) {
  oudbord* hulp=new oudbord;
  int i;
  int j;
  for (i=0;i<x;i++)
    for (j=0;j<y;j++)
      hulp->C[i][j]=A[i][j];
  if (eerste==NULL)
    eerste=hulp;
  if (laatste!=NULL)
    hulp->vorige=laatste;
  else
    hulp->vorige=NULL;
  laatste=hulp;
} // stapel::zetopstapel

// haal een bord van de stapel
void stapel::haalvanstapel (int A[ ][n], int x, int y) {
  oudbord* hulp=laatste;
  int i;
  int j;
  if (hulp->vorige!=NULL) {
    laatste=hulp->vorige;
    delete hulp;
    hulp=laatste;
    for (i=0;i<x;i++)
      for (j=0;j<y;j++)
        A[i][j]=hulp->C[i][j];
  } // if
} // stapel::haalvanstapel

//verwijder de hele stapel
void stapel::verwijderstapel ( ) {
  oudbord* hulp=laatste;
  while (laatste!=NULL) {
    laatste=laatste->vorige;
    delete hulp;
    hulp=laatste;
  } // while
} // stapel::verwijderstapel  
  
int main ( ) {
  int x; // kolommen
  int y; // rijen
  char z; // keuzechar
  int player; // de kleur van de speler
  int diepte = 4; // de recursieve diepte
  bool slim=true; // moet de computer slim zijn of niet
  int p; // x-coordinaat
  int q; // y-coordinaat
  bool goedezet=false;
  bool zetterug=false;
  leegscherm ( );
  //infoblok();
  cout << "Welkom bij Othello!" << endl;
  cout << "Met welke kleur wilt u spelen? ([z]wart of [w]it) ";
  cin >> z;
  if (z=='W' || z=='w')
    player=1;
  else
    player=0;
  cout << endl << endl; 
  cout << "Hoe groot wilt u het bord hebben waar u op gaat spelen?" << endl;
  cout << "Aantal rijen (maximaal 20, minimaal 4): ";
  cin >> y;
  if(y < 4)
    y = 4;
  else if(y > 20)
    y = 20;
  cout << "Aantal kolommen (maximaal 20, minimaal 4): ";
  cin >> x;
  if(x < 4)
    x = 4;
  else if(x > 20)
    x = 20;
  cout << endl << endl;
  cout << "Wilt u dat de computer [s]limme of [r]andom zetten doet? ";
  cin >> z;
  if (z=='R' || z=='r')
    slim=false;
  else {
    slim=true;
    cout << "Hoeveel stappen moet de computer dan vooruit denken?" << endl
         << "(Niet meer dan 15) ";
    cin >> diepte;
    if(diepte > 15)
      diepte = 15;
    else if(diepte < 1)
      diepte = 1;
  }
  bord nieuw (x, y, diepte);
  stapel zet;
  zet.eerste=NULL;
  zet.laatste=NULL;
  zet.zetopstapel (nieuw.A, x, y);
  nieuw.beurt=0;
  leegscherm ( );
  nieuw.drukaf ( );
  cout << endl << endl;
  while (nieuw.zetmogelijk ( )) {
    zetterug=false;
    if (nieuw.beurt==player) {
      cout << endl << "Jij bent aan de beurt om een zet te doen" << endl
           << "(Voer 0 in om een zet terug te nemen)" << endl;	
      while (!goedezet) {
        cout << "Geef het x-coordinaat: ";
        cin >> p;
        if (p<1)
          p = 1;
        else if (p>x)
          p = x;
      	if (p==0) {
      	  zetterug=true;
      	  goedezet=true;
      	} // if
      	if (p==-1)
      	  return 0;
      	if (!zetterug) {
      	  cout << "En het y-coordinaat: ";	
      	  cin >> q;
      	  if (q<1)
            q = 1;
          else if (q>y)
            q = y;
          if (nieuw.toegestanezet (p-1, q-1))
  	        goedezet=true;
  	      else
  	        cout << "Dit is geen geldige zet, probeer opnieuw" << endl;
      	} // if
      } // while
      goedezet=false;
      leegscherm ( );
      cout << "Jouw zet " << endl;
    } // if  
    else {
      if (slim)
        nieuw.slimmezet (p, q);
      else
        nieuw.randomzet (p, q);	
      cout << endl << "De computerzet " << endl;
    }
    if (zetterug)
      zet.haalvanstapel (nieuw.A, x, y);
    else {
      nieuw.doezet (p-1, q-1);
      if (nieuw.beurt!=player)
        zet.zetopstapel (nieuw.A, x, y);
      nieuw.beurt=(nieuw.beurt+1)%2;
    } // else  
    cout << "(x:" << p << "),(y:" << q << "):" << endl;
    nieuw.drukaf ( );
  } // while
  nieuw.winnaar();
  //eindblok();
  return 0;
} // main