Как мне найти количество различных возможных матриц?

Question

Ссылка на актуальную проблему: - https://www.codechef.com/problems/TREASURE

Вам дана сетка с N строками (с номерами от 1 до N) и M столбцами (с номерами от 1 до M). Обозначим ячейку в строке 'r' и столбце 'c' через (r, c). Две ячейки сетки являются смежными, если они имеют общую сторону.

Некоторые ячейки этой сетки содержат сокровища. Вы не знаете точно, какие ячейки содержат их, но анализ сетки, названный картой поиска сокровищ, доступен. Для каждой ячейки (i, j) вам дается целое число A (i, j) со следующим значением:

A (i, j) = - 1: нет информации

A (i, j) = 0: существует четное количество ячеек, содержащих сокровище, которые находятся рядом с ячейкой (i, j).

A (i, j) = 1: существует нечетное количество ячеек, содержащих сокровища, которые находятся рядом с ячейкой (i, j).

(Примечание: -Ноль считается четным числом)

Схема сокровищ - это набор всех ячеек, содержащих сокровища. Найдите количество возможных раскладов сокровищ, которые соответствуют всей предоставленной информации.

Пример: -

Следующая (3 X 2) матрица: -

1 -1

1 -1

1 0

Ответ: - Количество возможных матриц равно «4».

Answer 1

Некоторые мысли, которые могут помочь в создании законченного решения. Глядя на пример,

1 -1
1 -1
1  0

y -1
1  x
x  0

Ноль означает, что два x являются четным экземпляром сокровищ, которые в любом случае фиксируют y с сокровищем, чтобы удовлетворить три ячейки, смежные с серединой слева 1:

T -1  or  T -1
1  -      1  T
-  0      T  0

Единственные две другие ячейки, которые имеют эффект - это верхняя и нижняя левая 1 с. Исправление одного подразумевает другое:

1  x  or  1  T
T  x      x  x
1  x      1  T

2 * 2 = 4

Как правило, ограничение возникает, когда две непосредственно диагональные ячейки или две линейные ячейки, разделенные третьей, не равны -1. Также можно заметить, что по существу существуют две независимые матрицы. Значения x s подразумевают расположение сокровищ только в o s и наоборот:

x o x o x
o x o x o
x o x o x