Найдите любые возможные две координаты прямоугольника, две координаты которого заданы

Дана матрица mat[][] размера N×N , где двумя элементами матрицы являются «1», обозначающая координату прямоугольника, и «0», обозначающая пустое пространство, задача состоит в том, чтобы найти две другие координаты прямоугольника. .
Примечание . Для этой задачи может быть несколько ответов, выведите любой из них.

Примеры:

 Input: mat[][] = {{0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}
Output: {{0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 0, 0}, {0, 0, 0, 0}}
Explanation: 
0 0 1 1 
0 0 1 1
0 0 0 0
0 0 0 0
The coordinates {{0, 2}, {0, 3}, {1, 2}, {1, 3}} forms the rectangle

Input: mat[][] = {{0, 0, 1, 0}, {0, 0, 0, 0}, {1, 0, 0, 0}, {0, 0, 0, 0}} 
Output: {{1, 0, 1, 0}, {0, 0, 0, 0}, {1, 0, 1, 0}, {0, 0, 0, 0}}

Подход: оставшуюся координату можно найти, используя эти заданные координаты, потому что некоторые точки могут иметь общую строку, а некоторые могут иметь общий столбец. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте две пары, скажем, p1 и p2 , чтобы сохранить позицию 1 в исходной матрице mat[].
• Инициализируйте две пары, скажем, p3 и p4 , чтобы сохранить позицию, в которую должна быть вставлена новая 1 , чтобы сделать ее прямоугольником.
• Пройдите через матрицу, используя два вложенных цикла, и найдите пары p1 и p2 .
• Теперь возможны три случая:
  • Если p1.first и p2.first одинаковы, в этом случае добавление 1 к p1.first и p2.first дает нам p3.first и p4.first , в то время как p3.second и p4.second остаются такими же, как p1.second и p2. второй соответственно.
  • Если p1.second и p2.second одинаковый в этом случае добавление 1 к p1.second и p2.second дает нам p3.second и p4.second , в то время как p3.first и p4.first остаются такими же, как p1.first и p2.first
  • Если нет одинаковых координат, то p3.first = p2.first , p3.second = p1.second , p4.first = p1.first и p4.second = p2.second .
• Замените координаты p3 и p4 на 1 и распечатайте матрицу.

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

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