Cod sursa(job #2221)

Utilizator aLiNuSh-LTDTomescu Alin aLiNuSh-LTD Data 16 decembrie 2006 15:07:10
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.56 kb
#include <fstream>
#include <iostream>
#include <cstdlib>
using namespace std;

long tabla[17][17]; //tabla de joc
long btabla[17][17];
long a[17][17];
unsigned int n,m;   //dimensiunile tablei de joc
long long smax = 0;

void ReadData ()
{
    register unsigned int i,j;
    
    fstream fin("flip.in", ios::in);
    fin >> n;
    fin >> m;
    for ( i = 0; i < n; ++i )
        for ( j = 0; j < m; ++j )
        {
           fin >> tabla[i][j];
           //btabla[i][j] = tabla[i][j];
        }
    fin.close();
}

void WriteData ()
{
    fstream fout("flip.out", ios::out);
    fout << smax;
    fout.close();
}

void ShowData ()
{
    register unsigned int i,j;
    cout << "-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-" << endl;
    for ( i = 0; i < n; ++i )
    {
      for ( j = 0; j < m; ++j )
      {
         cout << tabla[i][j] << " ";
      }
      cout << endl << endl;
    }
    cout << "Suma = " << smax << endl;
}

void FlipColumn (unsigned int j)
{
     register unsigned int i;
     for (i = 0; i < m; i++)
     {
         a[i][j] *= -1;
     }
}

void FlipRow (unsigned int i)
{
     register unsigned int j;
     for (j = 0; j < n; j++)
     {
         a[i][j] *= -1;
     }
}

void InitMatrix (long x)
{
     register unsigned int i,j;
     for (i = 0; i < n; i++)
     {
       for (j = 0; j < m; j++)
       {
           a[i][j] = x;
       }
     }
}
void FlipMatrix ()
{
     register unsigned int i,j;
     for (i = 0; i < n; i++)
     {
       for (j = 0; j < m; j++)
       {
           btabla[i][j] = a[i][j] * tabla[i][j];
       }
     }
}

long long SumMatrix ()
{
     long long s = 0;
     register unsigned int i,j;
     for (i = 0; i < n; i++)
     {
       for (j = 0; j < m; j++)
       {
           s += tabla[i][j];
       }
     }
     return s;
}

class BT
{
      private:
          long st[17];
          long k;
          long n;
          long m;
      protected:
          void Init ();
          bool areSuccesor ();
          bool eValid ();
          void Afisare ();
          bool Solutie ();
          void StartBT ();          
      public:
          bool isSolution;
          bool Next ();
          long *GetStack () { return st; }
          long GetStackLength () { return m; }             
          BT (long x);
};
void BT::Init ()
{ 
     if (k > 1) 
     { 
          st[k] = st[k-1];
     }
     else st[k] = 0;
}
void BT::Afisare ()
{
     for (long i = 1; i <= m; i++)
     {
         cout << st[i] << "; ";
     }
     cout << endl;
}
bool BT::Solutie ()
{
     return k == m;
}
bool BT::areSuccesor ()
{
     if (st[k] < n)
     {
          st[k]++;
          return true;
     }
     return false;
}

bool BT::eValid ()
{
     return true;
}
void BT::StartBT ()
{    
     Init ();
}
bool BT::Next ()
{
     bool ok;
     isSolution = false;
     while (k > 0)
     {
          do
          {
              
          } while ((ok = areSuccesor ()) && !eValid ());
          
          if (ok)
          {      
              if (Solutie())
              {              
                  isSolution = true;
              }
              else
              {
                  k++;
                  Init ();
              }
          }
          else
          {              
              k--;
          }
          
          if (k == 0)
          { 
              m++; k = 1; Init ();
          }
          if (m > n) 
          {
              break; 
          }
          else return true;
     }
     return false;  
}
BT::BT (long x)
    : k (1), n (x), m (1)
{    
     StartBT ();
/*     bool ok;
     
     
     while (k > 0)
     {
          do
          {
              
          } while ((ok = areSuccesor ()) && !eValid ());
          
          if (ok)
          {      
              if (Solutie())
              {              
                  Afisare ();
              }
              else
              {
                  k++;
                  Init ();
              }
          }
          else
          {              
              k--;
          }
          
          if (k == 0) 
          { 
              m++; k = 1; Init (); 
          }
          if (m > n) 
          {
              break; 
          }
     }   */
}

int main(void)
{      
    InitMatrix (1);       
    ReadData ();
    //ShowData ();
    
    BT r(6);
    long *str;
    long *stc;
    long mr;
    long mc;
    while (r.Next ())
    {
        if (r.isSolution)
        {
            BT c(6);
            while (c.Next ())
            {
                  if (c.isSolution)
                  {
                      str = r.GetStack ();
                      mr = r.GetStackLength ();
                      stc = c.GetStack ();
                      mc = c.GetStackLength ();

                      for (int i = 0; i < mr; i++)
                      {
                         FlipRow (str[i]-1);
                         for (int j = 0; j < mc; j++)
                         {
                              FlipColumn (stc[j]-1);
                              FlipMatrix ();
                              int sum = SumMatrix ();
                              if (sum > smax) smax = sum;
                         }
                         InitMatrix (1);
                      }
                  }
            }    
        }
    }
    
    WriteData ();
    
    system("PAUSE");
    return(0);
}