Проекция
Проекция
Все знают, что вы фанат TensorFlow. Поэтому перед вами стояла задача воссоздать логотип TensorFlow из двух проекций.
Пусть у Вас имеется трехмерный объем размера n * m * h, и две проекции (две матрицы с размерами n * m и n * h с элементами 0 и 1). Вас просят вычислить возможные наборы кубов, которые должны быть размещены внутри 3D-объема таким образом, чтобы 3D-объект, созданный с помощью кубов, отбрасывал тени, указанные матрицами проекций, когда свет падает слева и спереди. Если это невозможно, просто выведите -1. Если это возможно, Вы должны найти ровно два набора, один с максимальным количеством кубиков и один с минимальным количеством. Вы можете предположить, что гравитации нет (кубы расположены внутри 3D-объема именно там, где они размещены, не требуя никакой поддержки). Считаем, что 1 представляет тень, а 0 представляет свет.
Если таких решений несколько, выведите лексикографически минимальное. Решение a лексикографически меньше решения b, если первое число, отличающееся между двумя решениями, в a меньше, чем в b.
Например, решение [(0, 0, 0), (1, 1, 1)] меньше решения [(1, 1, 1), (0, 0, 0)].
Входные данные
В первой строке записаны три целых числа n, m, h (1 ≤ n, m, h ≤ 100) - размеры пространства.
Каждая из следующих n строк содержит m символов, каждый из которых представляет либо 1 (область тени), либо 0 (область света). Матрица описывает проекцию предмета спереди.
Каждая из следующих n строк содержит h символов в том же формате, что и выше, описывающих проекцию предмета слева.
Выходные данные
В первой строке выведите одно число: либо -1 если решения нет, либо kmax
- максимальное количество кубов, которые можно расположить в пространстве, которые будут генерировать две проекции, заданные во входных данных.
Следующие kmax
строк должны содержать тройки чисел x, y, z (0 ≤ x < n, 0 ≤ y < m, 0 ≤ z < h), представляющие кубы, выбранные в лексикографически наименьшем решении с максимальным количеством кубов . В случае существования решения следует вывести еще одну строку, содержащуя kmin
- минимальное количество кубов, которое мы можем расположить в пространстве, которые будут генерировать две проекции, заданные во входных данных.
Следующие kmin
строк должны содержать тройки чисел x, y, z (0 ≤ x < n *, *0 ≤ y < m, 0 ≤ z < h), представляющие кубы в лексикографически наименьшем решении с минимальным числом кубов.
Пояснение
Куб с координатами (x, y, z) создаст тень в строке x и столбце y в n * m проекции и тень в строке x и столбце z в проекции n * h (индексируется с 0).
5 3 3 111 010 010 010 010 111 100 110 100 100
14 0 0 0 0 0 1 0 0 2 0 1 0 0 1 1 0 1 2 0 2 0 0 2 1 0 2 2 1 1 0 2 1 0 2 1 1 3 1 0 4 1 0 8 0 0 0 0 1 1 0 2 2 1 1 0 2 1 0 2 1 1 3 1 0 4 1 0