Pranka
Национална Олимпиада по Информатика 2010, Кръг 3
Time Limit: 1s, Memory Limit: 128MiB
Посещавайки курса по Проектиране и Анализ на Компютърни Алгоритми, или накратко ПРАНКА, Ели забелязва следното явление. Докато преподавателят пише код по дъската и е с гръб към студентите, те започват да скучаят и в най-честия случай - да си говорят.

Все пак в старанието си да са сравнително тихи, всеки от тях си говори с най-много един от преките си съседи отляво, отдясно, отпред или отзад. Това означава, че няма двама души, които да си говорят през ред или през колона, както и няма човек, който да си говори с двама или повече души едновременно. Някои от седалките в залата, където се води курсът (зала 200, ФМИ) са счупени, съответно на тях няма хора. Въпреки всичко, двама човека на един ред или колона не могат да си говорят през счупена седалка отново по съображения за запазване на (относителна) тишина.

Елеонора забелязва, че някои от хората остават „изолирани”, тоест техните съседи или вече си говорят с някой друг или са прекалено далеч поради счупени седалки. Разглеждайки залата, Ели вижда, че ако двойките говорещи си хора се бяха разпределили по друг начин то не би имало изолирани студенти. Например нека разгледаме следните две разположения върху 2 реда и 4 колони:
A A B B може да бъде A B B C C # # D A # # C

Докато в левия случай студентите C и D са изолирани, в десния всеки е включен в разговор. С “#” са отбелязани счупени седалки.

Разположение, в което има начин да няма изолирани хора, Ели нарича „перфектно”. За да не скучае, тя решава да провери дали хората на първия ред са в перфектно разположение, после хората на първия и втория ред, после хората на първия, втория и третия ред и т.н.

Напишете програма, която намира колко перфектни разположения е намерила Ели. С други думи, ако залата има N реда, то за кои числа KN хората от първи до K-ти ред биха могли да си говорят без да има изолирани студенти.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и M, съответно броят редове и броят колони на залата. На следващите N реда ще има по M символа, които са или '.', отбелязващ човек, или '#', отбелязващ счупена седалка.
Изход
На първия ред на стандартния изход изведете колко перфектни разположения е намерила Ели. На втория ред, разделени с по един интервал, изпечатайте в нарастващ ред числата Кi, за които разположенията от първи до Кi-ти ред са перфектни. Ако няма нито едно перфектно разположение, то на един единствен ред изпечатайте 0.
Ограничения
  • 1 ≤ N ≤ 1000
  • 1 ≤ M ≤ 20
Примерен Вход Примерен Изход
9 4 .... .##. .#.. ##.# #.## .... ...# .##. .... 5 1 2 4 7 9
Имаме зала с 9 реда и 4 колони. От всички 36 места, 12 седалки са счупени. Има 5 перфектни разпределения, които са съответно самият първи ред, до втори ред, до четвърти ред, до седми ред, както и до девети ред (тоест цялата зала).
Примерни разпределения биха били:
До 1ви ред До 2ри ред До 4ти ред До 7ми ред До 9ти ред
AABB
ABBC
A##C
AABB
C##D
C#ED
##E#
AABB
C##D
C#ED
##E#
#F##
GFHH
GII#
AABB
C##D
C#ED
##E#
#F##
GFHH
GII#
J##K
JLLK
Мрън!