Question

Să considerăm o matrice cu N linii şi N coloane cu elemente numere naturale. În această matrice trebuie să plasăm două ture, în poziţii distincte. Spunem că un element al matricei este atacat dacă se află pe aceeaşi linie sau pe aceeaşi coloană cu una dintre cele două ture. Elementele din poziţiile celor două ture nu sunt considerate atacate.
Turele vor fi plasate astfel încât suma elementelor atacate să fie cât mai mare.

Cerința
Scrieţi un program care să determine suma elementelor atacate (maximă posibil).

Date de intrare
Fișierul de intrare ture.in va conţine pe prima linie un număr natural N, cu semnificaţia din enunţ. Pe fiecare dintre următoarele N linii se află câte N numere naturale, reprezentând elementele matricei.

Date de ieșire
Fișierul de ieșire ture.out va conţine o singură linie pe care va fi scrisă suma maximă.

Restricții și precizări
2 ≤ N ≤ 100
Elementele matricei sunt numere naturale mai mici sau egale cu 255



Exemplu
ture.in

5
4 2 2 3 3
4 2 1 4 0
1 3 4 0 1
4 3 0 2 3
0 0 3 0 4
ture.out

40
Explicație
Prima tură va fi plasată în poziţia (4,3), iar cea de a doua tură va fi plasată în poziţia (2,5).

Answer 1

#include <fstream>

#include <iostream>

using namespace std;

ifstream fin("ture.in");

ofstream fout("ture.out");

 

int n, v[101][101], suml[101], sumcol[101], k, maxi, sumeij[101][101];

void citire() {

 int x;

 fin >> n;

 for (int i = 1; i <= n; i++)

   for (int j = 1; j <= n; j++) {

     fin >> x;

     suml[i] += x;

     sumcol[j] += x;

     v[i][j] = x;

   }

}

 

void calc_sume() {

 for (int i = 1; i <= n; i++)

   for (int j = 1; j <= n; j++) {

     sumeij[i][j] = suml[i] + sumcol[j] - 2 * v[i][j];

     for (int ii = 1; ii <= i - 1; ii++)

       for (int jj = 1; jj <= n; jj++)

         if (ii != i && jj != j)

           maxi =

               max(sumeij[ii][jj] + sumeij[i][j] - v[ii][j] - v[i][jj], maxi);

         else

           maxi = max(sumeij[ii][jj] + sumeij[i][j] - sumcol[j], maxi);

     for (int jj = 1; jj <= j - 1; jj++)

       maxi = max(sumeij[i][jj] + sumeij[i][j] - suml[i], maxi);

   }

}

 

void afisare() { fout << maxi; }

 

int main() {

 citire();

 calc_sume();

 afisare();

 

 return 0;

}