Рассмотрим вначале слова четной длины. Заметим, что можем поменять местами любые две группы из двух символов, которыя начинается с четной позиции. А еще можем поменять местами символы в любой такой группе. Таким образом сортируем строки. Например: dcab => abcd. Если отсортированные строки совпали, то вычеркиваем их. Теперь для нечетной длины: важно, чтобы совпадали последние символы. Можно, например, приписать в конце '$' и решать для них задачу точно так же.

UPD: Ай, упало.

Переберём за 2^h, какие горизонтали будем вычёркивать. Это можно сделать, например, при помощи битовых масок или рекурсивно.

Зафиксировав горизонтали, найдём все вертикали, в которых осталось что-то невычеркнутое (эти вертикали мы вычеркнуть обязаны).

Теперь, зная номера вертикалей и горизонталей, которые собираемся вычеркнуть, посчитаем отдельно для одних и для других, какое минимальное количество блоков нам понадобится использовать. Утверждается, что это можно делать жадно: перебираем линии в порядке увеличения номера и, если текущую линию обязательно вычёркивать, вычеркнем её, иначе — вычеркнем в том и только в том случае, если непосредственно перед ней мы вычеркнули хотя бы одну линию, но количество вычеркнутых линий не образует целое число блоков. То есть, например, если R = 4, то, если мы вычеркнули уже 7 горизонталей подряд, то вычеркнем и 8-ю, а если уже вычеркнули 8, то текущую (которую вычёркивать необязательно) вычёркивать не будем, т.к. предыдущие образуют два целых блока и нам ни к чему начинать третий.

Ответ — минимум по всем вариантам, которые мы перебрали.

Круче был бы такой сэмпл: {"topcoder", "otpcoder", "topcoder", "otpcoder","topcoder", "otpcoder","topcoder", "otpcoder","topcoder", "otpcoder", "**koloterrorita**", "redocpot", "doretopc", "cpotdoer", "otpcoder", "cpotoder", "dotopcer", "recpotod", "ercpotod", "pcreotod", "toercpod", "dopcreot", "odpcreot", "cpdoreot", "erodpcot", "tocpdore"}