Задача №111148. Раскрашивание
На планете Олимпия ежегодно проводится традиционная игра в «Раскраски». Местом проведения этой игры является большое олимпийское поле N × M, каждая клетка которого окрашена в белый или в черный цвет. Двое игроков ходят по очереди, и суммарно совершают на двоих ровно K ходов. Во время своего хода игроку разрешается закрасить собственным цветом все клетки любого одного прямоугольника чья высота и ширина не превышает D. Первый игрок закрашивает клетки в белый цвет, а второй — в черный. По окончании K-го хода подсчитывается окончательный счет игры — количество клеток каждого цвета. Победителем оглашается тот игрок, в чей цвет раскрашено большее число клеток чем у соперника. Поэтому, целью каждого игрока есть максимизация количества клеток его собственного цвета в окончательном варианте раскраски поля.
Напишите программу, которая по начальной раскраске, количеству ходов и ограничениям на прямоугольник, который может закрашивать игрок, найдет окончательный счет игры при оптимальной стратегии обоих игроков.
Первая строка входного файла содержит четыре натуральных числа: N, M, D и K (N ≤ 400, M ≤ 400, D ≤ 400, K ≤ 109) — высота и ширина поля, ограничение на размер прямоугольника, который может закрашивать игрок, количество ходов, которые предстоит выполнить до подведения окончательного счета. В последующих N строках расположено по M символов: W если соответствующая клетка раскрашена в белый цвет и B, в случае если клетка поля раскрашена в черный цвет.
Единственная строка выходного файла должна содержать два целых числа — количество белых и количество черных клеток в окончательном варианте раскраски при условии оптимальной игры обоих игроков.
3 3 2 1
BWB
BBW
WBB
6 3
Подзадача 1. N, M, D, K ≤ 100. Решение оценивается в 50 баллов.
Подзадача 2. Дополнительные ограничения отсутствуют. Решение оценивается в 50 баллов.