#include <stdio.h> #include <stdlib.h> #include <math.h> #include <iostream> #include <stack> #include <list> using namespace std; const int Noir = 0; const int Blanc = 1; const int Vide = 2; const int Exterieur = 3; const int Taille = 15; const int TailleAlignement = 4; unsigned long long HashArray [2] [Taille + 2] [Taille + 2]; class Connect { public: char goban [Taille + 2] [Taille + 2]; unsigned long long hash; Connect () { hash = 0; for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) goban [i] [j] = Vide; for (int i = 0; i < Taille + 2; i++) { goban [0] [i] = Exterieur; goban [i] [0] = Exterieur; goban [Taille + 1] [i] = Exterieur; goban [i] [Taille + 1] = Exterieur; } } void initHash () { for (int c = 0; c < 2; c++) for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) { HashArray [c] [i] [j] = 0; for (int b = 0; b < 64; b++) if ((rand () / (RAND_MAX + 1.0)) > 0.5) HashArray [c] [i] [j] |= (1ULL << b); } } void joue (int x, int y, int couleur) { goban [x] [y] = couleur; hash ^= HashArray [couleur] [x] [y]; } void dejoue (int x, int y, int couleur) { goban [x] [y] = Vide; hash ^= HashArray [couleur] [x] [y]; } bool gagne (int x, int y, int couleur) { int nb [8] = {0}; for (int i = 1; i < TailleAlignement; i++) { if (nb [0] == i - 1) if (goban [x] [y - i] == couleur) nb [0]++; if (nb [1] == i - 1) if (goban [x + i] [y - i] == couleur) nb [1]++; if (nb [2] == i - 1) if (goban [x + i] [y] == couleur) nb [2]++; if (nb [3] == i - 1) if (goban [x + i] [y + i] == couleur) nb [3]++; if (nb [4] == i - 1) if (goban [x] [y + i] == couleur) nb [4]++; if (nb [5] == i - 1) if (goban [x - i] [y + i] == couleur) nb [5]++; if (nb [6] == i - 1) if (goban [x - i] [y] == couleur) nb [6]++; if (nb [7] == i - 1) if (goban [x - i] [y - i] == couleur) nb [7]++; } if ((1 + nb [0] + nb [4] >= TailleAlignement) || (1 + nb [1] + nb [5] >= TailleAlignement) || (1 + nb [2] + nb [6] >= TailleAlignement) || (1 + nb [3] + nb [7] >= TailleAlignement) ) return true; return false; } bool gameOver () { return false; } }; Connect connect; const int Infini = 10000000; int couleurProuvante = Noir; class Noeud { public: char x, y; int pn, dn; list<Noeud *> listeFils; void init () { listeFils.clear (); } void descente (Connect & connect, int couleur); }; const int MaxNoeud = 10000000; int nbNoeuds = MaxNoeud; Noeud racine; Noeud pileNoeud [MaxNoeud]; void Noeud::descente (Connect & connect, int couleur) { int autre = Noir; if (couleur == Noir) autre = Blanc; if (listeFils.size () == 0) { for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) if (connect.goban [i] [j] == Vide) { connect.joue (i, j, couleur); nbNoeuds--; if (nbNoeuds < 0) { cout << "plus de memoire" << endl; exit (0); } Noeud * n = &pileNoeud [nbNoeuds]; n->init (); n->x = i; n->y = j; if (connect.gagne (i, j, couleur)) { if (couleur == couleurProuvante) { n->pn = 0; n->dn = Infini; } else { n->pn = Infini; n->dn = 0; } } else { n->pn = 1; n->dn = 1; } listeFils.push_back (n); connect.dejoue (i, j, couleur); } } else { Noeud * meilleurFils = NULL; for (list<Noeud *>::iterator iter = listeFils.begin (); iter != listeFils.end (); ++iter) { if (couleur == couleurProuvante) { if ((*iter)->pn == pn) { meilleurFils = *iter; break; } } else if ((*iter)->dn == dn) { meilleurFils = *iter; break; } } connect.joue (meilleurFils->x, meilleurFils->y, couleur); meilleurFils->descente (connect, autre); connect.dejoue (meilleurFils->x, meilleurFils->y, couleur); } if (couleur == couleurProuvante) { pn = Infini; dn = 0; for (list<Noeud *>::iterator iter = listeFils.begin (); iter != listeFils.end (); ++iter) { if ((*iter)->pn < pn) pn = (*iter)->pn; dn += (*iter)->dn; } } else { pn = 0; dn = Infini; for (list<Noeud *>::iterator iter = listeFils.begin (); iter != listeFils.end (); ++iter) { if ((*iter)->dn < dn) dn = (*iter)->dn; pn += (*iter)->pn; } } } class NoeudTranspo { public: char x, y; int pn, dn; list<NoeudTranspo *> listeFils; unsigned long long hash; void init () { listeFils.clear (); } void descente (Connect & connect, int couleur); }; const int MaxNoeudTranspo = 10000000; int nbNoeudsTranspo = MaxNoeudTranspo; NoeudTranspo racineTranspo; NoeudTranspo pileNoeudTranspo [MaxNoeudTranspo]; void NoeudTranspo::descente (Connect & connect, int couleur) { int autre = Noir; if (couleur == Noir) autre = Blanc; if (listeFils.size () == 0) { for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) if (connect.goban [i] [j] == Vide) { connect.joue (i, j, couleur); nbNoeudsTranspo--; if (nbNoeudsTranspo < 0) { cout << "plus de memoire" << endl; exit (0); } NoeudTranspo * n = &pileNoeudTranspo [nbNoeudsTranspo]; n->init (); n->x = i; n->y = j; n->hash = connect.hash; if (connect.gagne (i, j, couleur)) { if (couleur == couleurProuvante) { n->pn = 0; n->dn = Infini; } else { n->pn = Infini; n->dn = 0; } } else { n->pn = 1; n->dn = 1; } listeFils.push_back (n); connect.dejoue (i, j, couleur); } } else { NoeudTranspo * meilleurFils = NULL; for (list<NoeudTranspo *>::iterator iter = listeFils.begin (); iter != listeFils.end (); ++iter) { if (couleur == couleurProuvante) { if ((*iter)->pn == pn) { meilleurFils = *iter; break; } } else if ((*iter)->dn == dn) { meilleurFils = *iter; break; } } connect.joue (meilleurFils->x, meilleurFils->y, couleur); meilleurFils->descente (connect, autre); connect.dejoue (meilleurFils->x, meilleurFils->y, couleur); } if (couleur == couleurProuvante) { pn = Infini; dn = 0; for (list<NoeudTranspo *>::iterator iter = listeFils.begin (); iter != listeFils.end (); ++iter) { if ((*iter)->pn < pn) pn = (*iter)->pn; dn += (*iter)->dn; } } else { pn = 0; dn = Infini; for (list<NoeudTranspo *>::iterator iter = listeFils.begin (); iter != listeFils.end (); ++iter) { if ((*iter)->dn < dn) dn = (*iter)->dn; pn += (*iter)->pn; } } } const int TailleTable = 65535; class Table { public: list<NoeudTranspo *> table [TailleTable + 1]; NoeudTranspo * present (unsigned long long hash) { for (list<NoeudTranspo *>::iterator iter = table [hash & TailleTable].begin (); iter != table [hash & TailleTable].end (); iter++) if ((*iter)->hash == hash) return *iter; return NULL; } void ajoute (NoeudTranspo *n) { table [n->hash & TailleTable].push_back (n); } void clear () { for (int i = 0; i < TailleTable + 1; i++) table [i].clear (); } }; Table table; class NoeudCarre { public: char x, y; int pn, dn; list<NoeudCarre *> listeFils; unsigned long long hash; void init () { listeFils.clear (); } void descente (Connect & connect, int couleur); }; const int MaxNoeudCarre = 10000000; int nbNoeudsCarre = MaxNoeudCarre; NoeudCarre racineCarre; NoeudCarre pileNoeudCarre [MaxNoeudCarre]; void NoeudCarre::descente (Connect & connect, int couleur) { int autre = Noir; if (couleur == Noir) autre = Blanc; if (listeFils.size () == 0) { for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) if (connect.goban [i] [j] == Vide) { connect.joue (i, j, couleur); nbNoeudsCarre--; if (nbNoeudsCarre < 0) { cout << "plus de memoire" << endl; exit (0); } NoeudCarre * n = &pileNoeudCarre [nbNoeudsCarre]; n->init (); n->x = i; n->y = j; n->hash = connect.hash; if (connect.gagne (i, j, couleur)) { if (couleur == couleurProuvante) { n->pn = 0; n->dn = Infini; } else { n->pn = Infini; n->dn = 0; } } else { racine.init (); nbNoeuds = MaxNoeud; racine.descente (connect, couleur); int nb = 1; while ((racine.pn != 0) && (racine.pn != Infini) && (nb < 1000)) { racine.descente (connect, couleur); nb++; } n->pn = racine.pn; n->dn = racine.dn; } listeFils.push_back (n); connect.dejoue (i, j, couleur); } } else { NoeudCarre * meilleurFils = NULL; for (list<NoeudCarre *>::iterator iter = listeFils.begin (); iter != listeFils.end (); ++iter) { if (couleur == couleurProuvante) { if ((*iter)->pn == pn) { meilleurFils = *iter; break; } } else if ((*iter)->dn == dn) { meilleurFils = *iter; break; } } connect.joue (meilleurFils->x, meilleurFils->y, couleur); meilleurFils->descente (connect, autre); connect.dejoue (meilleurFils->x, meilleurFils->y, couleur); } if (couleur == couleurProuvante) { pn = Infini; dn = 0; for (list<NoeudCarre *>::iterator iter = listeFils.begin (); iter != listeFils.end (); ++iter) { if ((*iter)->pn < pn) pn = (*iter)->pn; dn += (*iter)->dn; } } else { pn = 0; dn = Infini; for (list<NoeudCarre *>::iterator iter = listeFils.begin (); iter != listeFils.end (); ++iter) { if ((*iter)->dn < dn) dn = (*iter)->dn; pn += (*iter)->pn; } } } int solve () { racine.init (); nbNoeuds = MaxNoeud; racine.descente (connect, Noir); int nb = 1; while ((racine.pn != 0) && (racine.pn != Infini)) { cout << racine.pn << " "; racine.descente (connect, Noir); nb++; } cout << "resultat : pn = " << racine.pn << " en " << nb << " descentes" << endl; return racine.pn; } int solveTranspo () { racineTranspo.init (); nbNoeudsTranspo = MaxNoeudTranspo; racineTranspo.descente (connect, Noir); int nb = 1; while ((racineTranspo.pn != 0) && (racineTranspo.pn != Infini)) { cout << racineTranspo.pn << " "; racineTranspo.descente (connect, Noir); nb++; } cout << "resultat : pn = " << racineTranspo.pn << " en " << nb << " descentes" << endl; return racineTranspo.pn; } int solveCarre () { racineCarre.init (); nbNoeudsCarre = MaxNoeudCarre; racineCarre.descente (connect, Noir); int nb = 1; while ((racineCarre.pn != 0) && (racineCarre.pn != Infini)) { cout << racineCarre.pn << " "; racineCarre.descente (connect, Noir); nb++; } cout << "resultat : pn = " << racineCarre.pn << " en " << nb << " descentes" << endl; return racineCarre.pn; } int main () { connect.initHash (); cout << solveCarre () << endl; }