ACM SEERC 2009. The Computer Game Problem

Мне кажется, эту задачу можно решить динамикой по профилю, но необходимость связности точек всё усложняет. Никто ничего не посоветует?

Да.
И еще, надо повернуть систему координат на 45 градусов чтобы избежать таймлимита

На примере этой задачи:
   Представь что ты начинаешь заполнять свои точки сверху вниз. Тогда для каждой строки тебе важно знать что находилось только на предыдущей строке, и не больше (т.к. связи с предпредыдущей быть не может). Получается динамика вида F[I, J], где I - номер строки, J - "рваный" профиль, и F[I, J] - количество таких способов. J - это маска, только уже не битовая. В данной задаче, как я вижу (я пока ещё не писал), J это разбитие текущей строки по группам. Например для битовой 1010111 соответствует массиву 1 0 2 0 3 3 3, а после того как перейдем по 1110101 получится массив 1 1 1 0 2 0 2. Надо только в этом случае правильно рассмотреть все возможные и невозможные случаи перехода.

P.S. Но это как я понял, возможно и не так.

зачем дописывать под одной клетке? дописывай сразу строку, т.е. все возможные варианты 2^, и пробуй дописать все возможные строки, и количество компонент вродь как не надо, в конце же должна одна компонента остаться, один тип, а при добавление строки мы контролируем чтобы не распадалось на две компоненты и в дальнейшем могло слиться в одну. ну и как сказал alt нужно повернуть, но мне кажется оптимизированное решение должно и без поворота успеть, там с поворотам нехорошие случаи возникают.

* o o o * -> 1 0 0 0 2
после добавление строки * o o o * комбинация останется такой же 1 0 0 0 2,
после добавление * * * * * комбинация превратся в 1 1 1 1 1,
потом если снова будет добавлять * o o o * комбинация будет уже такой 1 0 0 0 1,
а потом если добавим * o * o * комбинация станет такой 1 0 2 0 1,
добавим * o * * * комбинация станет 1 0 1 1 1.