Rezolvare completă PbInfo #3244 tabla

O tablă de șah de dimensiune n x n conține pe toate pătrățelele câte o piesă cu una din culorile: alb, negru, roșu, verde sau albastru. Pe tablă nu există 3 piese consecutive pe aceeași linie sau coloană de aceeași culoare. O mutare presupune interschimbarea a două piese alăturate, fie pe o linie, fie pe o coloană. După mutare se acordă punctaj dacă se obțin următoarele situații și nu numai:

  • 3 piese de aceeași culoare consecutive pe o linie sau o coloană = 1 punct;
  • 3 piese de aceeași culoare consecutive pe o linie și o coloană = 5 puncte;

La orice situație de mai sus, o piesă în plus de aceeași culoare mai contribuie cu încă 1 la punctaj. De exemplu, 4 piese de aceeași culoare consecutive pe o linie sau o coloană = 2 puncte. Punctajele obținute de piesele interschimbate se adună. Punctajul este 0 dacă nu se obțin măcar 3 piese consecutive de aceeași culoare.

Cerința

Găsiți cel mai mare punctaj obținut în urma unei singure mutări.

Date de intrare

Fișierul de intrare tabla.in conține, pe prima linie, numărul natural n, ce reprezintă dimensiunea tablei. Pe fiecare dintre următoarele n linii se află câte n valori separate prin spatii. Valorile posibile pot fi: 1, 2, 3, 4 și 5. Valoarea 1 reprezintă piesa de culoare albă, 2 piesa de culoare neagră etc.

Date de ieșire

Fișierul de ieșire tabla.out va conține cel mai mare punctaj obținut.

Restricții și precizări

  • 1 ≤ n ≤ 20

Exemplul 1:

tabla.in

3
1 1 2
2 2 1
3 4 5

tabla.out

2

Explicație

Prin interschimbarea elementului (1,3) cu (2,3) se obține:
1 1 1
2 2 2
3 4 5
și am 1 punct din prima linie și 1 punct din a doua linie

Exemplul 2:

tabla.in

6
1 2 4 2 1 5
1 2 4 2 4 4
4 4 3 4 4 1
3 3 4 3 3 5
1 1 3 1 1 2
1 1 3 1 1 2

tabla.out

14

Explicație

Prin interschimbarea elementului (3,3) cu (4,3) se obține:
1 2 4 2 1 5
1 2 4 2 4 4
4 4 4 4 4 1
3 3 3 3 3 5
1 1 3 1 1 2
1 1 3 1 1 2
și am 7 (5+2) puncte de la piesele codificate cu 4 și 7 puncte de la piesele codificate cu 3.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema tabla:

#include <fstream>

using namespace std;
ifstream f("tabla.in");
ofstream g("tabla.out");
int a[22][22],n,vmax,pt;
void sch(int i1,int j1,int i2,int j2)
{
    int aux;
    aux=a[i1][j1];
    a[i1][j1]=a[i2][j2];
    a[i2][j2]=aux;
}
int orizontal(int i,int j)
{    int p=0,k;
    //dreapta
    k=j+1;
    while(a[i][k]==a[i][j])
    {
        p++;k++;
    }
    //stanga
    k=j-1;
    while(a[i][k]==a[i][j])
    {
        p++;k--;
    }
    return p;
}
int vertical(int i,int j)
{    int p=0,k;
    //jos
    k=i+1;
    while(a[k][j]==a[i][j])
    {
        p++;k++;
    }
    //sus
    k=i-1;
    while(a[k][j]==a[i][j])
    {
        p++;k--;
    }
    return p;
}

void rezolvao(int i,int j)  //vecini orizontal
{int nr[5]={0},t;
    sch(i,j,i,j+1);
    pt=0;
    nr[1]=orizontal(i,j);
    nr[2]=vertical(i,j);
    nr[3]=orizontal(i,j+1);
    nr[4]=vertical(i,j+1);
    for(t=1;t<=4;t++)
        if(nr[t]>=2)pt=pt+1+nr[t]-2;
    if(nr[1]>=2 &&nr[2]>=2)pt=pt+3;
    if(nr[3]>=2&&nr[4]>=2)pt=pt+3;
    if(pt>vmax)vmax=pt;
    sch(i,j,i,j+1);
    }
void rezolvav(int i,int j)  //vecini vertical
{int nr[5]={0},t;
    sch(i,j,i+1,j);
    pt=0;
    nr[1]=orizontal(i,j);
    nr[2]=vertical(i,j);
    nr[3]=orizontal(i+1,j);
    nr[4]=vertical(i+1,j);
    for(t=1;t<=4;t++)
        if(nr[t]>=2)pt=pt+1+nr[t]-2;
    if(nr[1]>=2&&nr[2]>=2)pt=pt+3;
    if(nr[3]>=2&&nr[4]>=2)pt=pt+3;
    if(pt>vmax)vmax=pt;
    sch(i,j,i+1,j);
}
int main()
{    int i,j;
    //citire
    f>>n;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            f>>a[i][j];
    //bordare
    for(i=0;i<=n+1;i++)
        a[i][0]=a[0][i]=a[n+1][i]=a[i][n+1]=6;
    vmax=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            //vecini pe linie
            if(a[i][j+1]<6 &&a[i][j]!=a[i][j+1])
                rezolvao(i,j);
            //vecini pe coloana
            if(a[i+1][j]<6 && a[i][j]!=a[i+1][j])
                rezolvav(i,j);

        }
    g<<vmax<<endl;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #3244 tabla

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3244 tabla de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!