Codeforces Round 746 (Div. 2) |
---|
Закончено |
Разница между версиями заключается в стоимости операций. Решение для одной версии не будет работать для другой!
У Алисы есть таблица размером $$$n \times m$$$, изначально все ее клетки окрашены в белый цвет. Клетка на пересечении $$$i$$$-й строки и $$$j$$$-го столбца обозначается как $$$(i, j)$$$. Алиса может выполнять следующие операции:
Выбрать любой подпрямоугольник, содержащий клетку $$$(1, 1)$$$, и инвертировать цвета всех его клеток. (Инвертировать означает изменить цвет клетки с белого на черный или с черного на белый).
Эта операция стоит $$$1$$$ монету.
Выбрать любой подпрямоугольник, содержащий клетку $$$(n, 1)$$$, и инвертировать цвета всех его клеток.
Эта операция стоит $$$3$$$ монеты.
Выбрать любой подпрямоугольник, содержащий клетку $$$(1, m)$$$, и инвертировать цвета всех его клеток.
Эта операция стоит $$$4$$$ монеты.
Выбрать любой подпрямоугольник, содержащий клетку $$$(n, m)$$$, и инвертировать цвета всех его клеток.
Эта операция стоит $$$2$$$ монеты.
Напомним, что подпрямоугольник — это все клетки $$$(x, y)$$$ с $$$x_1 \le x \le x_2$$$, $$$y_1 \le y \le y_2$$$ для некоторых $$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le m$$$.
Алиса хочет получить свою любимую раскраску с помощью этих операций. Какое наименьшее количество монет ей придется потратить? Можно показать, что всегда можно преобразовать исходную таблицу в любую другую.
Первая строка ввода содержит $$$2$$$ целых числа $$$n, m$$$ ($$$1 \le n, m \le 500$$$) — размеры таблицы.
В $$$i$$$-й из следующих $$$n$$$ строк содержится строка $$$s_i$$$ длины $$$m$$$, состоящая из букв W и B. $$$j$$$-й символ строки $$$s_i$$$ - W, если клетка $$$(i, j)$$$ окрашена в белый цвет в любимой раскраске Алисы, и B, если она окрашена в черный цвет.
Выведите наименьшее количество монет, которое Алиса должна будет потратить, чтобы получить свою любимую раскраску.
3 3 WWW WBB WBB
2
10 15 WWWBBBWBBBBBWWW BBBBWWWBBWWWBBB BBBWWBWBBBWWWBB BBWBWBBWWWBBWBW BBBBWWWBBBWWWBB BWBBWWBBBBBBWWW WBWWBBBBWWBBBWW WWBWWWWBBWWBWWW BWBWWBWWWWWWBWB BBBWBWBWBBBWWBW
68
В первом примере оптимально просто применить четвертую операцию один раз к прямоугольнику, содержащему клетки $$$(2, 2), (2, 3), (3, 2), (3, 3)$$$. Это обойдется в $$$2$$$ монеты.
Название |
---|