Проверить, можно ли сделать две матрицы строго возрастающими, поменяв местами только соответствующие значения

Опубликовано: 8 Октября, 2022

Даны две матрицы размера n * m A[][] и B[][] , задача состоит в том, чтобы сделать обе матрицы строго возрастающими (и по строкам, и по столбцам), только заменив местами два элемента в разных матрицах, если они расположены в соответствующей позиции т.е. A[i][j] можно поменять местами только с B[i][j] . Если возможно, то выведите Yes , иначе No.
Примеры:

Input: 
A[][] = {{2, 10},      B[][] = {{9, 4},  
         {11, 5}}               {3, 12}}
Output: Yes
Swap 2 with 9 and 5 with 12 then the resulting 
matrices will be strictly increasing.

Input: 
A[][] = {{1, 3},       B[][] = {{3, 1}, 
         {2, 4},                {3, 6}, 
         {5, 10}}               {4, 8}}
Output: No

Подход: мы можем решить эту проблему, используя жадный метод. Поменяйте местами A[i][j] с B[i][j] , если A[i][j] > B[i][j] . В конце для каждого i и j мы имеем A[i][j] ≤ B[i][j] .
Если результирующие матрицы строго возрастают, то выведите Yes , иначе выведите No.
Ниже приведена реализация вышеуказанного подхода:

Сложность по времени: O(N*M), так как мы проходим по матрице.

Вспомогательное пространство: O(1), так как мы не используем дополнительное пространство.

РЕКОМЕНДУЕМЫЕ СТАТЬИ