Dada una array mat[][] de dimensión N*M que está ordenada por filas y columnas , la tarea es encontrar la suma de los elementos de la array reemplazando todos los 0 en la array con cualquier valor tal que el la array permanece ordenada por filas y por columnas . Si no es posible, imprima “-1” .
Nota: los 0 solo estarán presentes en las celdas internas. es decir, ni en la primera fila o columna ni en la última fila o columna.
Ejemplos:
Entrada: mat[][] = {{3, 4, 5, 6}, {4, 0, 7, 8}, {6, 8, 0, 10}, {7, 9, 10, 12}}
Salida : 116
Explicación:
La nueva array formada después de reemplazar ceros es:
[[3, 4, 5, 6],
[4, 7, 7, 8],
[6, 8, 10, 10],
[7, 9, 10 , 12]]
que está ordenado y tiene una suma máxima, es decir, 116Entrada: mat[][] = {{1, 2, 4}, {2, 0, 5}, {5, 6, 7}}
Salida: 37
Enfoque: para ordenar la array y también para maximizar las sumas, los ceros se pueden reemplazar por un número que sea menor o igual que el siguiente elemento en su fila o columna. Dado que el valor de cero a cambiar depende del valor de su siguiente fila y columna, el reemplazo debe hacerse desde el final de la array. Por lo tanto, recorra la array desde el final y reemplace las celdas donde mat[i][j] es cero con min(mat[i][j + 1], mat[i + 1][j]) y también verifique el nuevo la array está ordenada o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum sum of
// the given matrix after replacing 0s
// with any element
int findMaximumSum(int* mat, int n, int m)
{
// Traverse the given matrix from
// the end
for (int i = n - 2; i > 0; i--) {
for (int j = m - 2; j > 0; j--) {
// If the element is 0
if (mat[i * m + j] == 0) {
// Replace the 0s
mat[i * m + j]
= min(mat[i * m + (j + 1)],
mat[(i + 1) * m + j]);
}
}
}
// Stores the sum of matrix elements
int sum = 0;
// Traverse the matrix mat[][]
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Updating the sum
sum += mat[i * m + j];
// Checking if not sorted
if ((i + 1 < n
&& mat[i * m + j]
> mat[(i + 1) * m + j])
|| (j + 1 < m
&& mat[i * m + j]
> mat[i * m + (j + 1)])) {
return -1;
}
}
}
// Return the maximum value of the sum
return sum;
}
// Driver Code
int main()
{
int N = 3, M = 3;
int mat[N][M]
= { { 1, 2, 4 }, { 2, 0, 5 }, { 5, 6, 7 } };
cout << findMaximumSum((int*)mat, N, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Driver Code
public static void main(String[] args)
{
int[][] mat
= { { 1, 2, 4 }, { 2, 0, 5 }, { 5, 6, 7 } };
System.out.println(findMaximumSum(mat));
}
// Function to find the maximum sum of
// the given matrix after replacing 0s
// with any element
public static int findMaximumSum(int[][] mat)
{
int N = mat.length;
int M = mat[0].length;
// Traverse the given matrix from
// the end
for (int i = N - 2; i > 0; i--) {
for (int j = M - 2; j > 0; j--) {
// If the element is 0
if (mat[i][j] == 0) {
// Replace the 0's
mat[i][j] = Math.min(mat[i][j + 1],
mat[i + 1][j]);
}
}
}
// Stores the sum of matrix elements
int sum = 0;
// Traverse the matrix mat[][]
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// Updating the sum
sum += mat[i][j];
// Checking if not sorted
if ((i + 1 < N && mat[i][j] > mat[i + 1][j])
|| (j + 1 < M
&& mat[i][j] > mat[i][j + 1]))
return -1;
}
}
// Return the maximum value of the sum
return sum;
}
}
// This code is contributed by Kdheeraj.
Python3
# python program for the above approach # Function to find the maximum sum of # the given matrix after replacing 0s # with any element def findMaximumSum(mat, n, m): # Traverse the given matrix from # the end for i in range(n-2, 0, -1): for j in range(m-2, 0, -1): # If the element is 0 if (mat[i][j] == 0): # Replace the 0s mat[i][j] = min(mat[i][(j + 1)], mat[(i + 1)][j]) # Stores the sum of matrix elements sum = 0 # Traverse the matrix mat[][] for i in range(0, n): for j in range(0, m): # Updating the sum sum += mat[i][j] # Checking if not sorted if ((i + 1 < n and mat[i][j] > mat[(i + 1)][j]) or (j + 1 < m and mat[i][j] > mat[i][(j + 1)])): return -1 # Return the maximum value of the sum return sum # driver code N = 3 M = 3 mat = [[1, 2, 4], [2, 0, 5], [5, 6, 7]] print(findMaximumSum(mat, N, M)) # This code is contributed by amreshkumar3
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the maximum sum of
// the given matrix after replacing 0s
// with any element
static int findMaximumSum(int[, ] mat, int n, int m)
{
// Traverse the given matrix from
// the end
for (int i = n - 2; i > 0; i--) {
for (int j = m - 2; j > 0; j--) {
// If the element is 0
if (mat[i, j] == 0) {
// Replace the 0s
mat[i, j] = Math.Min(mat[i, (j + 1)],
mat[(i + 1), j]);
}
}
}
// Stores the sum of matrix elements
int sum = 0;
// Traverse the matrix mat[][]
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Updating the sum
sum += mat[i, j];
// Checking if not sorted
if ((i + 1 < n
&& mat[i, j] > mat[(i + 1), j])
|| (j + 1 < m
&& mat[i, j] > mat[i, (j + 1)])) {
return -1;
}
}
}
// Return the maximum value of the sum
return sum;
}
// Driver Code
public static void Main()
{
int N = 3, M = 3;
int[, ] mat
= { { 1, 2, 4 }, { 2, 0, 5 }, { 5, 6, 7 } };
Console.WriteLine(findMaximumSum(mat, N, M));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the maximum sum of
// the given matrix after replacing 0s
// with any element
function findMaximumSum(mat, n, m)
{
// Traverse the given matrix from
// the end
for (let i = n - 2; i > 0; i--) {
for (let j = m - 2; j > 0; j--) {
// If the element is 0
if (mat[i][j] == 0) {
// Replace the 0s
mat[i][j]
= Math.min(mat[i][j + 1],
mat[i + 1][j]);
}
}
}
// Stores the sum of matrix elements
let sum = 0;
// Traverse the matrix mat[][]
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
// Updating the sum
sum += mat[i][j];
// Checking if not sorted
if ((i + 1 < n
&& mat[i][j]
> mat[i + 1][j])
|| (j + 1 < m
&& mat[i][j]
> mat[i][(j + 1)])) {
return -1;
}
}
}
// Return the maximum value of the sum
return sum;
}
// Driver Code
let N = 3, M = 3;
let mat
= [[1, 2, 4], [2, 0, 5], [5, 6, 7]];
document.write(findMaximumSum(mat, N, M));
// This code is contributed by Potta Lokesh
</script>
37
Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)