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:
3piese de aceeași culoare consecutive pe o linie sau o coloană= 1punct;3piese de aceeași culoare consecutive pe o linie și o coloană= 5puncte;
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:
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:
3piese de aceeași culoare consecutive pe o linie sau o coloană= 1punct;3piese de aceeași culoare consecutive pe o linie și o coloană= 5puncte;
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.
#include <bits/stdc++.h>
using namespace std;
ifstream cin("tabla.in");
ofstream cout("tabla.out");
int a[21][21], n, cnt, b[21][21];
bool inmat(int i, int j)
{
return i <= n && j <= n && i >= 1 && j >= 1;
}
bool cont3pr(int i, int j){
if(a[i][j] == a[i-1][j] && a[i-1][j] == a[i-2][j] && inmat(i-2, j))
return 1;
if(a[i][j] == a[i-1][j] && a[i-1][j] == a[i+1][j] && inmat(i-1,j) && inmat(i+1, j))
return 1;
if(a[i][j] == a[i+1][j] && a[i+1][j] == a[i+2][j] && inmat(i+2, j))
return 1;
return 0;
}
bool cont3pl(int i, int j){
if(a[i][j] == a[i][j+1] && a[i][j+1] == a[i][j+2] && inmat(i, j+2))
return 1;
if(a[i][j] == a[i][j-1] && a[i][j-1] == a[i][j+1] && inmat(i, j-1) && inmat(i, j+1))
return 1;
if(a[i][j] == a[i][j-1] && a[i][j-1] == a[i][j-2] && inmat(i, j-2))
return 1;
return 0;
}
void transfB(int i, int j){
if(a[i][j] == a[i-1][j] && a[i-1][j] == a[i-2][j] && inmat(i-2, j))
b[i][j] = b[i-1][j] = b[i-2][j] = 1;
else if(a[i][j] == a[i-1][j] && a[i-1][j] == a[i+1][j] && inmat(i+1, j) && inmat(i-1, j))
b[i][j] = b[i-1][j] = b[i+1][j] = 1;
else if(a[i][j] == a[i+1][j] && a[i+1][j] == a[i+2][j] && inmat(i + 2, j))
b[i][j] = b[i+1][j] = b[i+2][j] = 1;
if(a[i][j] == a[i][j-1] && a[i][j-1] == a[i][j-2] && inmat(i, j-2))
b[i][j] = b[i][j-1] = b[i][j-2] = 1;
else if(a[i][j] == a[i][j+1] && a[i][j+1] == a[i][j-1] && inmat(i, j-1) && inmat(i, j+1))
b[i][j] = b[i][j+1] = b[i][j-1] = 1;
else if(a[i][j] == a[i][j+1] && a[i][j+1] == a[i][j+2] && inmat(i, j+2))
b[i][j] = b[i][j+1] = b[i][j+2] = 1;
}
bool ladr3(int i, int j){
bool ok = false;
if(a[i][j] == a[i][j-1] && a[i][j-1] == a[i][j-2] && inmat(i, j-2))
ok = true;
if(b[i][j] == b[i][j-1] && b[i][j-1] == b[i][j-2] && b[i][j] == 1 && inmat(i, j-2))
ok = false;
return ok;
}
bool lasus3(int i, int j){
bool ok = false;
if(a[i][j] == a[i-1][j] && a[i][j] == a[i-2][j] && inmat(i-2, j))
ok = true;
if(b[i][j] == b[i-1][j] && b[i][j] == b[i-2][j] && b[i][j] == 1 && inmat(i-2, j))
ok = false;
return ok;
}
void verif(int i, int j){
if(cont3pr(i, j) && cont3pl(i, j))
cnt+=5, transfB(i, j);
else if(ladr3(i, j))
cnt++;
else if(lasus3(i, j))
cnt++;
}
int di[]={0,1,-1,0};
int dj[]={-1,0,0,1};
int main(){
int max = 0;
cin >> n;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
cin >> a[i][j];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j){
int k, t;
for(int d = 0; d <= 3; ++d)
if(inmat(i + di[d], j + dj[d])){
k = i + di[d], t = j + dj[d];
cnt = 0;
swap(a[i][j], a[k][t]);
for(int q = 1; q <= n; ++q)
for(int w = 1; w <= n; ++w)
verif(q,w);
if(cnt > max)
max = cnt;
swap(a[i][j], a[k][t]);
for(int q = 1; q <= n; ++q)
for(int w = 1; w <= n; ++w)
b[q][w] = 0;
}
}
cout << max;
return 0;
}
