#include <iostream> #include <list> #include <algorithm> using namespace std; const int Taille = 9; const int JoueurGauche = 0; const int JoueurDroit = 1; class Intersection { public: int x, y; bool legale () { return ((x >= 0) && (x < Taille) && (y >= 0) && (y < Taille)); } }; class Coup { public: list<Intersection> l; friend istream & operator >> (istream & entree, Coup & c); friend ostream & operator << (ostream & sortie, Coup & c); }; istream & operator >> (istream & entree, Coup & c) { Intersection inter; entree >> inter.x >> inter.y; while (true) { c.l.push_back (inter); entree >> inter.x; if (inter.x == -1) break; entree >> inter.y; } return entree; } ostream & operator << (ostream & sortie, Coup & c) { for (list<Intersection>::iterator it = c.l.begin (); it != c.l.end (); ++it) sortie << "(" << it->x << "," << it->y << ")"; return sortie; } class Phutball { public: char damier [Taille] [Taille]; Intersection balle; Phutball () { init (); } void init () { for (int i = 0; i < Taille; i++) for (int j = 0; j < Taille; j++) damier [i] [j] = '+'; damier [Taille / 2] [Taille / 2] = '@'; balle.x = Taille / 2; balle.y = Taille / 2; } void joue (Coup & c) { list<Intersection>::iterator it = c.l.begin (); if (c.l.size () == 1) damier [it->x] [it->y] = 'O'; else { list<Intersection>::iterator precedent; while (true) { precedent = it; it++; if (it == c.l.end ()) break; damier [precedent->x] [precedent->y] = '+'; } if (precedent->legale ()) { damier [precedent->x] [precedent->y] = '@'; balle = *precedent; } } } void dejoue (Coup & c) { list<Intersection>::iterator it = c.l.begin (); if (c.l.size () == 1) { damier [it->x] [it->y] = '+'; } else { damier [balle.x] [balle.y] = '+'; balle = *it; it++; list<Intersection>::iterator precedent; while (true) { precedent = it; it++; if (it == c.l.end ()) break; damier [precedent->x] [precedent->y] = 'O'; } damier [balle.x] [balle.y] = '@'; } } bool gagne (int joueur, Intersection inter) { if (((joueur == JoueurDroit) && (inter.x < 0)) || ((joueur == JoueurDroit) && inter.legale () && (inter.x == 0)) || ((joueur == JoueurGauche) && (inter.x > Taille - 1)) || ((joueur == JoueurGauche) && inter.legale () && (inter.x == Taille - 1))) return true; return false; } bool coupsLegaux (int joueur, list<Coup> & liste) { for (int i = 0; i < Taille; i++) for (int j = 0; j < Taille; j++) if (damier [i] [j] == '+') { Intersection inter; inter.x = i; inter.y = j; Coup coup; coup.l.push_back (inter); liste.push_back (coup); } Coup coup; coup.l.push_back (balle); damier [balle.x] [balle.y] = '+'; bool gagne = coupsBalle (joueur, coup, liste); damier [balle.x] [balle.y] = '@'; return gagne; } bool coupsBalle (int joueur, Coup & coup, list<Coup> & liste) { bool coupGagnant = false; for (int i = -1; i <= 1; i++) for (int j = -1; j <= 1; j++) { Intersection inter = balle; inter.x += i; inter.y += j; if (inter.legale ()) if (damier [inter.x] [inter.y] == 'O') { Coup coup1 = coup; list<Intersection> pierresEnlevees; while (true) { coup1.l.push_back (inter); pierresEnlevees.push_back (inter); inter.x += i; inter.y += j; if ((inter.x < 0) || (inter.x >= Taille) || (inter.y < 0) || (inter.y >= Taille) || (damier [inter.x] [inter.y] != 'O')) break; } if (gagne (joueur, inter)) { coup1.l.push_back (inter); liste.push_back (coup1); coupGagnant = true; } else if (inter.legale ()) { if (damier [inter.x] [inter.y] == '+') { // on memorise la place de la balle Intersection ancienneBalle = balle; // on deplace la balle balle = inter; // on enleve les pierres sautees for (list<Intersection>::iterator it = pierresEnlevees.begin (); it != pierresEnlevees.end (); ++it) damier [it->x] [it->y] = '+'; // on ajoute le nouveau coup Coup coup2 = coup1; coup2.l.push_back (inter); liste.push_back (coup2); // on regarde les coups suivants if (coupsBalle (joueur, coup1, liste)) coupGagnant = true; // on remet les pierres enlevees for (list<Intersection>::iterator it = pierresEnlevees.begin (); it != pierresEnlevees.end (); ++it) damier [it->x] [it->y] = 'O'; // on remet la balle balle = ancienneBalle; } else cerr << "bug coupsBalle \n"; } } } return coupGagnant; } friend ostream & operator << (ostream & sortie, Phutball & v); }; ostream & operator << (ostream & sortie, Phutball & v) { sortie << " "; for (int i = 0; i < Taille; i++) sortie << i << " "; sortie << endl; for (int i = 0; i < Taille; i++) { sortie << i << " "; for (int j = 0; j < Taille; j++) sortie << v.damier [j] [i] << " "; sortie << endl; } return sortie; } Phutball phutball; int adversaire (int joueur) { if (joueur == JoueurGauche) return JoueurDroit; return JoueurGauche; } bool gagnant (int joueur, int n) { if (phutball.gagne (joueur, phutball.balle)) return true; list<Coup> listeCoups, listeCoupsAdverses; if (phutball.coupsLegaux (joueur, listeCoups)) return true; if (n == 0) return false; for (list<Coup>::iterator it = listeCoups.begin (); it != listeCoups.end (); ++it) { bool menaceVerifiee = false; phutball.joue (*it); if (gagnant (joueur, n - 1)) { menaceVerifiee = true; int autre = adversaire (joueur); if (phutball.coupsLegaux (autre, listeCoupsAdverses)) menaceVerifiee = false; for (list<Coup>::iterator it1 = listeCoupsAdverses.begin (); (it1 != listeCoupsAdverses.end ()) && menaceVerifiee; ++it1) { phutball.joue (*it1); if (!gagnant (joueur, n - 1)) menaceVerifiee = false; phutball.dejoue (*it1); } } phutball.dejoue (*it); if (menaceVerifiee) return true; } return false; } int main () { list<Coup> listeCoups; while (true) { cout << phutball; listeCoups.clear (); if (phutball.coupsLegaux (JoueurGauche, listeCoups)) { cout << "j'ai gagne !" << endl; break; } for (int l = 0; l < 3; l++) cout << "test gagnant " << l << " = " << gagnant (JoueurGauche, l) << endl; Coup coupAleatoire; int i = 0, indice = rand () % listeCoups.size (); for (list<Coup>::iterator it = listeCoups.begin (); it != listeCoups.end (); ++it) { if (i == indice) { coupAleatoire = *it; break; } i++; } cout << "Je joue en " << coupAleatoire << endl; phutball.joue (coupAleatoire); cout << phutball; listeCoups.clear (); if (phutball.coupsLegaux (JoueurDroit, listeCoups)) { cout << "vous avez gagne !" << endl; break; } Coup coup; cin >> coup; phutball.joue (coup); } return 0; }