Сенсорные панели
(Время: 3 сек. Память: 32 Мб Сложность: 78%)
На заводе выпускаются крупные интерактивные панели для промышленного оборудования. Поверхность такой панели разбита на прямоугольную сетку из миниатюрных сенсорных модулей размером N×M. Перед установкой каждая панель проходит финальную бесконтактную проверку: инженер направляет диагностический лазер от одного контрольного модуля к другому и фиксирует отклик системы. Не все модули панели устроены одинаково. Некоторые модули являются контрольными – их необходимо проверить обязательно. Некоторые закрыты защитным экраном – через них лазер не проходит вообще. Остальные модули служебные: на них не требуется получать отклик, но луч может пройти через них без помех. Из-за особенностей стенда панель закреплена в корпусе так, что переставлять оборудование между отдельными проверками нельзя. Поэтому инженер выбирает некоторый первый контрольный модуль, затем переводит луч на второй, потом на третий и так далее, пока не будут проверены все требуемые модули. Луч всегда идёт по прямому отрезку, соединяющему центры двух выбранных модулей. При этом действуют следующие технические ограничения:
- каждый контрольный модуль должен быть проверен ровно один раз;
- лазерный луч не может проходить через модуль с защитным экраном;
- если на прямом отрезке между двумя выбранными контрольными модулями находится центр другого контрольного модуля, то такой перевод луча допустим только в том случае, если этот промежуточный контрольный модуль уже был проверен ранее;
- служебные модули можно пересекать лучом, но выбирать их как точки проверки нельзя.
Инженеру нужно заранее оценить, сколько вообще существует допустимых сценариев полной инспекции. Это нужно для программирования стенда: если допустимых сценариев слишком мало, панели такого типа направляются на другую линию контроля с подвижным креплением. Для каждой из T панелей определите количество различных допустимых последовательностей проверки всех контрольных модулей. Две последовательности считаются различными, если на каком-то шаге выбирается разный следующий контрольный модуль.
Входные данные
В первой строке входного файла INPUT.TXT содержится натуральное число T (1 ≤ T ≤ 20). Далее идёт описание T панелей: два натуральных числа N, M (1 ≤ N, M ≤ 10), в N строках по M натуральных чисел ai,j (1 – контрольный модуль, 2 – модуль с защитным экраном, 3 – служебный модуль). Количество контрольных модулей является натуральных числом не более 18.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу для каждой панели с новой строки.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1
4 4
1 2 3 2
3 2 2 1
3 3 1 3
3 1 2 1 | 17 |
Пояснение к примеру:
Данную панель представим в следующем виде:
4 4
a1 a2 a3 a4
b1 b2 b3 b4
c1 c2 c3 c4
d1 d2 d3 d4
Возможные переходы:
1) a1 -> b4 -> d4 -> c3 -> d2
2) a1 -> d2 -> c3 -> b4 -> d4
3) a1 -> d2 -> c3 -> d4 -> b4
4) b4 -> a1 -> d2 -> c3 -> d4
5) b4 -> d4 -> c3 -> d2 -> a1
6) c3 -> d2 -> a1 -> b4 -> d4
7) c3 -> d4 -> b4 -> a1 -> d2
8) c3 -> d4 -> b4 -> d2 -> a1
9) d2 -> a1 -> b4 -> c3 -> d4
10) d2 -> a1 -> b4 -> d4 -> c3
11) d2 -> c3 -> d4 -> b4 -> a1
12) d4 -> b4 -> a1 -> d2 -> c3
13) d4 -> b4 -> c3 -> d2 -> a1
14) d4 -> c3 -> b4 -> a1 -> d2
15) d4 -> c3 -> b4 -> d2 -> a1
16) d4 -> c3 -> d2 -> a1 -> b4
17) d4 -> c3 -> d2 -> b4 -> a1
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
