Bubbles
Пролетен Турнир по Информатика, 2013
Time Limit: 5s, Memory Limit: 64MiB
В дългите и досадни часове по история Ели обича да играе на различни игри на телефона си. В момента нейната страст е играта Bubbles.

Играта има следните правила. В N реда, всеки от който съдържа M колони, са наредени разноцветни балони. Играта продължава K хода. На всеки ход Ели може да пукне някой от балоните, като освен него се пукат също така всички съседни по хоризонтала и вертикала балони със същия цвят, след това съседните на тях и така нататък, докато не остане съседен непукнат балон от този цвят. След като пукането на всички засегнати балони свърши (което може да считате, че става мигновено), евентуално някои от все още здравите балони ще останат без подпора (тоест балонът под тях е спукан). В тези случаи те почват да падат надолу, докато не стигнат земята или друг, все още непукнат балон.

Нека, например, имаме следната конфигурация (където различни главни букви отбелязват различни цветове балони) с 5 реда и 20 колони, като сме спукали балона с цвят 'A' (болд-нат в началната конфигурация):
AAAEECCCCBBBAAEEPTTR AAAAECAACAABBAAAKAAA ACCCCAAESPRITBBBBAAA AZCCCAAFAAABBBASSSAA ACCCCAAAAAAAAAVAAPAA AAAEECCCCBBBAAEEPTTR AAAAEC  CAABBAAAKAAA ACCCC  ESPRITBBBBAAA AZCCC  F   BBBASSSAA ACCCC         VAAPAA AAAEE         EEPTTR AAAAE      BAAAAKAAA ACCCC  CCBBBBABBBAAA AZCCCC ECAAITBASSSAA ACCCCCCFSPRBBBVAAPAA
Ако играчът е спукал P на брой балона в текущия ход, той печели P2 точки - тоест играта насърчава избирането (и създаването!) на по-големи групи балони с еднакъв цвят. Крайният резултат от играта е сумата на точките, получени на всеки от ходовете.

Ели иска да впечатли Станчо, който се слави с това, че пука много добре балоните в тази игра, но не му пука за Ели (pun intended). Знаейки началната конфигурация от балони, както и броя ходове, които може да направи, момичето иска да намери последователност от пукания, които биха й донесли максимален брой точки. Вие решавате да й помогнете, като напишете програма, която играе тази игра. Защо й помагате, след като най-много в следствие на това тя да се уреди със Станчо, остава мистерия.
Вход
На първия ред на стандартния вход съдържа три цели числа N, M и K - съответно броя редове и колони на таблицата, както и броя ходове, които трябва да направи Ели. Следват N реда, всеки съдържащ по M главни букви от английската азбука ({'A'-'Z'}). Забележете, че първият ред от балони на входя отговаря на най-горния ред!
Изход
На стандартния изход изведете K реда, всеки съдържащ по две цели числа - ред и колона, в които пукате балона на съответния ход. Индексирането започва от нула, като (0, 0) е клетката на таблицата долу вляво. Забележете, че понякога има смисъл два или повече пъти да цъкате в една и съща клетка, тъй като балоните биха могли да се пренаредят между ходовете. Разрешено е да цъкате в клетки, които вече не съдържат балон, като това не променя нищо и не ви носи точки. Такъв ход е удачен, ако например сте спукали всички балони.
Ограничения
  • 1 ≤ N, M, K ≤ 50
Оценяване
Решението ви ще бъде оценявано спрямо получените точки от авторското такова. Ако сте постигнали Y точки в играта, ще ви бъдат присъдени min(1, Y / А) * 10 точки за този тест - тоест пропорционално спрямо точките на авторското решение, в границите [0, 10].
Примерен Вход Примерен Изход
5 20 4 AAAEECCCCBBBAAEEPTTR AAAAECAACAABBAAAKAAA ACCCCAAESPRITBBBBAAA AZCCCAAFAAABBBASSSAA ACCCCAAAAAAAAAVAAPAA 1 8 0 0 0 1 3 18
3 23 11 AAAAAAAAAAAAAAAAAAAAAAA BCBCBCBCBCBCBCBCBCBCBCB AAAAAAAAAAAAAAAAAAAAAAA 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 2 22 0 0
Първият ход, направен в примерния изход, е примерът от условието, пукащ 18 балона с цвят 'A' в средата на дъската и носи 18*18 = 324 точки. Вторият ход пука друга група балони с цвят 'A', но този път в лявата страна на дъската. Групата съдържа 10 балона и носи 100 точки. Третият ход пука 14 балона с цвят 'C' и носи 196 точки. Последният ход пука отново 10 балона с цвят 'A', но този път в дясната част на дъската. Сумарно играчът е спечелил 324 + 100 + 196 + 100 = 720 точки в играта. В случая, авторското решение е успяло да спечели 1284 точки, като така играчът би получил 720 / 1284 * 10 = 5.60747664 точки за този тест.
Мрън!