Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 27.02.2010, 10:59
lanamelach

 
Сообщений: n/a

Количество способов размещения связанных точек
Задача "The Computer Game"
http://acmicpc-live-archive.uva.es/n...=sea&year=2009

Есть сетка, узлы которой имеют целочисленные координаты. 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
  #2  
Старый 06.03.2010, 18:51
lanamelach

 
Сообщений: n/a

Говорят, эта задача решается динамикой по изломанному профилю с поворотом системы координат на 45 градусов. Кто-нибудь может подсказать что в данном случае является изломанным профилем?
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Размещения - Нужна помощь! MaxFlow Математические алгоритмы 6 25.02.2010 15:27
Кол-во связанных вершин в орграфе гость Графы 4 02.10.2009 21:55
задача размещения: помогите!! Sanika Графы 7 14.03.2009 14:32
размещения с повторениями на с++ Норе Реализация, исходники, языки 3 14.11.2007 16:21
количество вариантов размещения шаров в корзинах BreakPoint Математические алгоритмы (другое) 10 11.07.2007 12:24