Тема: ACM SEERC 2009. The Computer Game Problem
Есть сетка, узлы которой имеют целочисленные координаты. M узлов этой сетки являются запрещенными, в остальные можно ставить точки, если координаты x и y точки удовлетворяют условию |x| + |y| < N. Точки можно ставить только в те узлы, которые еще свободны (т.е. все точки должны быть различны). Каждая пара точек должна иметь связь (возможно через другие точки). Две точки (x1, y1) и (x2, y2) считаются связанными, если |x1 – x2| + |y1 – y2| = 1.
Требуется определить количество способов, которыми можно разместить в узлах сетки произвольное положительное количество точек.
Входные данные:
T - количество тестов. Каждый тест начинается со строки, содержащей N и M. Следующие M строк содержат координаты x,y запрещенных узлов.
Выходные данные:
Для каждого теста вывести количество способов размещения точек.
Ограничения:
T = 74,
1 ? N ? 7,
1 ? M ? 225,
-7 ? Xk, Yk ? 7, все (Xk, Yk) различны.
время 4 с, память 256 мб.
Пример ввода:
2
2 1
7 7
2 3
0 0
4 -7
7 -4
Пример вывода:
20
4