Рассмотрим бесконечную сетку из единичных квадратов. Некоторые ячейки сетки являются планетами.
Мультивселенная M = {p1, p2, ..., pk} — это набор планет. Предположим, что есть бесконечный ряд или столбец со следующими двумя свойствами: 1) он не содержит ни одну планету pi из мультивселенной M; 2) по обе стороны от этого столбца или строки находятся планеты из M. В этом случае мы можем разбить мультивселенную M на две непустые мультивселенные M1 и M2, содержащие планеты, расположенные по соответствующую сторону этого ряда или столбца.
Мультивселенная, которую нельзя разделить, используя описанную выше операцию, называется вселенной. Мы выполняем операции, пока все мультивселенные не превратятся во вселенные.
Вам даны положения планет в изначальной мультивселенной. Найдите количество вселенных, которые появятся в результате описанного процесса. Можно доказать, что результат не зависит от порядка произведения операций.