2432 - Cruce

Se consideră o matrice pătratică de dimensiune N, conţinând numere naturale. Numim cruce de lăţime K reuniunea mulțimii tuturor elementelor aflate pe K linii consecutive ale matricei și a mulțimii tuturor elementelor aflate pe K coloane consecutive ale matricei. Două elemente ale matricei se consideră distincte dacă sunt situate pe poziții distincte în matrice. Se acceptă şi forma degenerată a unei cruci, în formă de T sau L, când una dintre liniile sau coloanele care formează crucea sunt chiar la marginea matricei. Vom defini valoarea unei cruci ca fiind suma elementelor din care aceasta este formată.

Cerința

Scrieți un program care, pentru o valoare K dată, determină o cruce de lățime K a cărei valoare este maximă și poziția ei în matrice. Această poziție va fi exprimată prin perechea de indici reprezentând prima linie din cele K consecutive și prima coloană din cele K consecutive din care este formată crucea.

Date de intrare

Fişierul cruce.in conţine pe prima linie numerele N şi K, iar pe următoarele N linii câte N numere întregi reprezentând în ordine, pe linii, elementele matricei. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul cruce.out va conţine trei numere Vmax L C, separate prin câte un spaţiu, reprezentând valoarea maximă determinată pentru o cruce de lățime K, respectiv linia și coloana care exprimă poziția acesteia în matrice.

Restricții și precizări

• 1 ≤ N ≤ 500
• 1 ≤ K < N
• Numerele din matrice sunt din intervalul [-5000, 5000]
• Liniile şi coloanele se indexează începând cu 1.
• Dacă există mai multe cruci de lățime K de valoare maximă, se va lua în considerare poziția cu indicele liniei mai mic, iar în caz de egalitate a liniilor poziția celei cu indicele coloanei mai mic.
• La olimpiadă s-au oferit 10 puncte din oficiu, aici vor fi date pe exemple.

Exemplu:

cruce.in

5 2
1 -2 3 -1 4
-3 2 2 -2 -1
1 2 3 4 5
1 0 -7 1 1
3 2 1 2 3

cruce.out

23 2 4

Explicație

Elementele ce formează crucea de valoare maxima sunt:

1 -2 3 -1 4

-3 2 2 -2 -1

1 2 3 4 5

1 0 -7 1 1

3 2 1 2 3

<syntaxhighlight lang="python" line="1"> def calculeaza_prefix_sum(matrice, N):

   prefix_sum = [[0] * (N + 1) for _ in range(N + 1)]
   for i in range(1, N + 1):
       for j in range(1, N + 1):
           prefix_sum[i][j] = matrice[i - 1][j - 1] \
                               + prefix_sum[i - 1][j] \
                               + prefix_sum[i][j - 1] \
                               - prefix_sum[i - 1][j - 1]
   return prefix_sum

def suma_submatrice(prefix_sum, x1, y1, x2, y2):

   return (prefix_sum[x2][y2]
           - prefix_sum[x1 - 1][y2]
           - prefix_sum[x2][y1 - 1]
           + prefix_sum[x1 - 1][y1 - 1])

def cruce_maxima(matrice, N, K):

   prefix_sum = calculeaza_prefix_sum(matrice, N)
   max_valoare = -1
   max_pos = (0, 0)
   
   for i in range(1, N - K + 2):
       for j in range(1, N - K + 2):
           # Suma liniilor K consecutive
           suma_linii = 0
           for r in range(K):
               suma_linii += suma_submatrice(prefix_sum, i + r, j, i + r, j + K - 1)
               
           # Suma coloanelor K consecutive
           suma_coloane = 0
           for c in range(K):
               suma_coloane += suma_submatrice(prefix_sum, i, j + c, i + K - 1, j + c)
               
           # Calculul valorii crucii
           suma_cruce = suma_linii + suma_coloane - suma_submatrice(prefix_sum, i, j, i + K - 1, j + K - 1)
           
           if suma_cruce > max_valoare:
               max_valoare = suma_cruce
               max_pos = (i, j)
   
   return max_valoare, max_pos

def main():

   import sys
   input = sys.stdin.read
   data = input().split()
   
   N = int(data[0])
   K = int(data[1])
   matrice = []
   
   index = 2
   for _ in range(N):
       matrice.append([int(x) for x in data[index:index + N]])
       index += N
   
   max_valoare, max_pos = cruce_maxima(matrice, N, K)
   print(max_valoare)
   print(max_pos[0], max_pos[1])

if __name__ == "__main__":

   main()

</syntaxhighlight>