Cod sursa(job #2967376)

Utilizator Anastasia7Anastasia Anastasia7 Data 19 ianuarie 2023 15:03:02
Problema Cuplaj maxim in graf bipartit Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.39 kb
#include <fstream>
#include <map>

using namespace std;
ifstream fin("xsizero.in");
ofstream fout("xsizero.out");

int tabla[3][3];
int rez[2000000];
int nrtotal=0;
int power3[10]={1,3,9,27,81,243,729,2187,6561,19683};
int rezultat[9][4]={
    {11, 12, 13},
    {21, 22, 23},
    {31, 32, 33},
    {11, 21, 31},
    {12, 22, 32},
    {13, 23, 33},
    {11, 22, 33},
    {13, 22, 31}
};
bool verif(int valoare)             //verifica daca x sau 0 au rezultatat rezultatJocul
{
    for (int i=0; i<8; i++)
        if (tabla[rezultat[i][0]/10][rezultat[i][0]%10] == valoare && tabla[rezultat[i][1]/10][rezultat[i][1]%10] == valoare && tabla[rezultat[i][2]/10][rezultat[i][2]%10] == valoare)
            return 1;
    return 0;
}
bool validareTabla()                 //se valideaza tabla
{
    int nrX=0, nr0=0;
    for (int i=1; i<=3; ++i)
        for (int j=1; j<=3; ++j)
        {
            if(tabla[i][j]==1)
                nrX++;
            if(tabla[i][j]==2)
                nr0++;
        }
    if (nrX!=nr0+1 && nrX!=nr0)    // numarul de x trebuie sa fie mai mare ca numarul O cu 1 sau numarul de x trebuie sa fie = cu numarul de O
        return 0;
    nrtotal=nr0+nrX;
    bool rezultataX=verif(1);
    bool rezultata0=verif(2);
    if(rezultataX==1 && rezultata0==0 && nrX==1+nr0)        //daca x a rezultatat trebuie sa fie cu un x mai mult
        return 1;
    if(rezultataX==0 && rezultata0==1 && nrX==nr0)               // daca 0 a rezultatat trebuie sa fie numar egal de x si 0
        return 1;
    if(rezultataX==0 && rezultata0==0)                      // daca nu a rezultatat niciunul rezultatJocul va continua
        return 1;
    return 0;
}
int rezultatJoc()
{
    int nrX=0, nr0=0;
    for(int i=1; i<=3; ++i)
        for(int j=1; j<=3; ++j)
        {
            if(tabla[i][j]==1)
                nrX++;
            if (tabla[i][j] == 2)
                nr0++;
        }
    int numar=0;
    for(int i=1; i<=3; i++)
        for(int j=1; j<=3; j++)
            numar+=tabla[i][j]*power3[(i-1)*3+j-1];         // calculam indexul situatiei de rezultatJoc in care suntem acum
    if (rez[numar]!=0)                                      // daca situatia de rezultatJoc are un rezultat atunci intoarcem rezultatul
        return rez[numar];
    bool rez1=verif(1);                                     // verificam daca a rezultatat x
    bool rez2=verif(2);                                     // verificam daca a rezultatat 0
    if (rez1==1 || rez2==1)                                 // rezultatJocul se termina daca a rezultatat x sau 0
    {
        if (nrX>nr0)
        {
            rez[numar]=1;
            return 1;
        }
        else
        {
            rez[numar]=2;
            return 2;
        }
    }
    if (nr0+nrX==9)                                         // nu mai sunt pozitii de completat
    {
        rez[numar]=3;
        return 3;
    }
    if (nrX==nr0)                                           // la rand este jucatorul cu x
    {
        rez[numar]=2;                                       // initalizam ca si cum jucatorul 0 rezultata
        for(int i=1; i<=3; ++i)
            for(int j=1; j<=3; ++j)
                if (tabla[i][j]==0)
                {
                    tabla[i][j]=1;
                    int mutareUrm=rezultatJoc();
                    if(mutareUrm==1)                        // daca un jucator ar urma sa rezultate rezultatJocul in urma mutarii
                        rez[numar]=1;
                    if(mutareUrm==3 && rez[numar]==2)       // daca un jucator ar urma sa faca egal in urma mutarii
                        rez[numar]=3;
                    tabla[i][j]=0;
                }
    }
    else                                                    // la rand este jucatorul cu 0
    {
        rez[numar]=1;                                       // initializam rezultatul ca si cum jucatorul cu 0 ar pierde
        for(int i=1; i<=3; i++)                             // luam pe rand mutarile pe care le poate face 0
            for(int j=1; j<=3; j++)
                if (tabla[i][j]==0)
                {
                    tabla[i][j]=2;
                    int mutareUrm=rezultatJoc();                    // calculam cum s-ar termina rezultatJocul daca 0 face acea mutare
                    if(mutareUrm==2)                        // rezultatJocul se termina cu victoria 0
                        rez[numar]=2;
                    if(mutareUrm==3 && rez[numar]==1)       // rezultatJocul se termina cu egalitate
                        rez[numar]=3;
                    tabla[i][j]=0;
                }
    }
    return rez[numar];
}

int main()
{
    map<char, int>carac;
    carac['.']=0;
    carac['X']=1;
    carac['0']=2;
    map<int,string> rezultat;
    rezultat[1]="win";
    rezultat[2]="lose";
    rezultat[3]="draw";
    string x,y,z;
    int nr=1;
    while(fin>>x>>y>>z)
    {
        for(int i=0; i<3; i++)
        {
            tabla[1][i+1]=carac[x[i]];
            tabla[2][i+1]=carac[y[i]];
            tabla[3][i+1]=carac[z[i]];
        }
        if(validareTabla()==0)
        {
            fout<<"Testul #"<<nr<<": invalid"<<"\n";
            nr++;
        }
        else
        {
            int jucator=rezultatJoc();
            fout<<"Testul #"<<nr<<": "<<rezultat[jucator]<<"\n";
            nr++;
        }
    }
    return 0;
}