Задача №113529. Arkady's Game
Аркадий и Алексей придумали новую игру. Листок клетчатой бумаги размером 2 N ×2 M клеток заполняется цифрами (по одной цифре в каждую клетку). Затем начинается собственно игра: тот, чья очередь ходить, разрезает листок пополам вдоль короткой стороны (или любой стороны, если листок квадратный), выбирает любую из половин и выбрасывает ее; оставшаяся половина передается другому игроку. При этом игрок получает очки за каждую пару клеток, бывших соседними до разрезания:
• если в соседних клетках были одинаковые цифры, то игрок получает 3 очка;
• если в соседних клетках были цифры одинаковой четности, то игрок получает 1 очко;
• если в соседних клетках были цифры разной четности, то игрок получает 0 очков.
Резать листок можно только по линиям, разделяющим клетки. Игра завершается, когда от листка остается одна клетка — ее разрезать нельзя. Побеждает тот, кто наберет больше очков. Аркадий ходит первым и его интересует, какую максимальную разницу между его очками и очками Алексея он может получить, если оба они будут играть оптимально. Аркадию и Алексею доступны только такие листки, у которых N и M отличаются не более чем на 1.
В первой строке записаны два целых числа N и M ( 0 ≤ N , M ≤ 10 , | N − M | ≤ 1 ). Данный листок имеет размеры 2 N ×2 M клеток. В следующих 2 N строках записано содержимое листка. В каждой строке записано 2 M десятичных цифр без пробелов. Каждая цифра соответствует одной клетке исходного листка.
Выведите единственное число — максимально возможную разницу между количествами очков Аркадия и Алексея.
В первом примере Аркадий может разрезать квадрат по горизонтали, получив 2 очка (за пары 1, 3 и 2, 4). Оставив Алексею половинку с цифрами 1, 2, Аркадий не даст ему шанса заработать ни одного очка. Если же Аркадий разрежет исходный квадрат по вертикали, то он не получит ни одного очка, зато при разрезании любой из оставшихся половин (
или Во втором примере Алексей наберет больше очков, как бы не играл Аркадий. Первым ходом Аркадий может только разрезать листок по вертикали, не получив очков. Если отдать Алексею левую половину, то это позволит ему получить 6 очков, разрезав ее по вертикали (за пары 2, 2 и 1, 1). При этом Аркадию достанется листок
, разрезание которого не принесет очков. Если же отдать Алексею правую половину исходного листка, то он сможет получить 1 очко, разрезав листок любым способом. Но для максимизации своего выигрыша Алексей разрежет листок по вертикали и отдаст Аркадию половинку
, разрезание которой не принесет последнему очков. Итоговый счет 0:1 в пользу Алексея.
1 1 12 34
2