Максимизируйте сумму матрицы, заменив 0, чтобы матрица оставалась отсортированной.

Дана матрица mat[][] размерности N*M , отсортированная по строкам и столбцам , задача состоит в том, чтобы найти сумму элементов матрицы, заменив все 0 в матрице любым значением таким, что матрица остается отсортированной по строкам и по столбцам . Если это невозможно, то выведите «-1» .

Примечание: нули будут присутствовать только во внутренних ячейках. т. е. ни в первой строке или столбце, ни в последней строке или столбце.

Примеры:

Input: mat[][] = {{3, 4, 5, 6}, {4, 0, 7, 8}, {6, 8, 0, 10}, {7, 9, 10, 12}}
Output: 116
Explanation:
The new matrix formed after replacing zeroes is:
[[3, 4, 5, 6], 
[4, 7, 7, 8], 
[6, 8, 10, 10], 
[7, 9, 10, 12]]
which is sorted and has a maximum sum i.e. 116

Input: mat[][] = {{1, 2, 4}, {2, 0, 5}, {5, 6, 7}}
Output: 37

Подход: Чтобы сделать матрицу отсортированной, а также максимизировать суммы, нули можно заменить числом, которое меньше или равно следующему элементу в его строке или столбце. Поскольку значение изменяемого нуля зависит от значения его следующей строки и столбца, замену следует производить с конца матрицы. Поэтому пройдите матрицу с конца и замените ячейки, где mat[i][j] равен нулю, на min(mat[i][j + 1], mat[i + 1][j]), а также проверьте новые матрица отсортирована или нет.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*M)
Вспомогательное пространство: O(1)