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

ture.out

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).

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 ture:

#include <bits/stdc++.h>
#define MAX 101
using namespace std;

int n;
int A[MAX][MAX];
int sl[MAX], sc[MAX];

int main()
{
  int i, j, r, c, r1, c1, r2, c2;
  int tmp, rez, max1, max2;
  freopen("ture.in", "r", stdin);
  freopen("ture.out", "w", stdout);

  scanf("%d", &n);
  for (i=1; i<=n; i++)
    for (j=1; j<=n; j++)
      {
        scanf("%d", &A[i][j]);
        sl[i]+=A[i][j];
        sc[j]+=A[i][j];
      }
  rez=0;
  //cazul 1
  for (r=1; r<=n; r++)
    for (c1=1; c1<=n; c1++)
      for (c2=1; c2<=n; c2++)
        {
          if (c1==c2) continue;
          tmp = sl[r] + sc[c1] + sc[c2] - 2*A[r][c1] - 2*A[r][c2];
          if (tmp > rez) rez = tmp;
        }
   //cazul 2
   for (c=1; c<=n; c++)
     for (r1=1; r1<=n; r1++)
       for (r2=1; r2<=n; r2++)
         {
           if (r1==r2) continue;
           tmp = sc[c] + sl[r1] + sl[r2] - 2*A[r1][c] - 2*A[r2][c];
           if (tmp > rez) rez = tmp;
         }
   //cazul 3
   for (r1=1; r1<=n; r1++)
     for (r2=1; r2<=n; r2++)
       {
         if (r1==r2) continue;
         max1 = -1000;
         for (c=1; c<=n; c++)
           {
             tmp = sc[c] - A[r2][c] - 2*A[r1][c];
             if (tmp > max1)
               {c1 = c; max1 = tmp; }
           }
         max2 = -1000;
         for (c=1; c<=n; c++)
           {
             tmp = sc[c] - A[r1][c] - 2*A[r2][c];
             if ((c!=c1) && (tmp > max2))
               {c2 = c; max2 = tmp; }
           }
         tmp = sl[r1] + sl[r2]
               + sc[c1] - A[r2][c1] - 2*A[r1][c1]
               + sc[c2] - A[r1][c2] - 2*A[r2][c2];
         if (tmp > rez) rez = tmp;
       }
  printf("%d", rez);

  fclose(stdout);
  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 #2211 ture

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2211 ture 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!

Rezolvare completă PbInfo #2211 ture