Клікоманія

Clickomania — це головоломка, у якій стартують із прямокутної сітки клітин різного кольору. На кожному кроці гравець вибирає («клікає») клітину. Усі з'єднані клітини того самого кольору, що й вибрана (включно з нею), видаляються, якщо вибрана клітина з'єднана хоча б з однією іншою клітиною того ж кольору. Утворену «дірку» заповнюють сусідні клітини за певним правилом, а метою гри є видалити всі клітини на полі. У цій задачі розглядається одномірна версія гри. Початковою точкою головоломки є рядок кольорів (кожен представлений великою латинською літерою).

У будь-який момент можна вибрати (клікнути) літеру, якщо така сама літера трапляється перед нею або після неї. Підрядок з однакових літер, що містить вибрану, видаляється, і рядок скорочується, прибираючи утворену дірку. Щоб розв’язати головоломку, гравець має видалити всі літери та отримати порожній рядок. Якщо після усіх дій залишається непорожній рядок, у якому вже не можна вибрати жодної літери, гравець програє. Наприклад, якщо стартувати з рядка $\text{ABBAABBAAB}$, вибір першої $\text{B}$ дає $\text{AAABBAAB}$. Далі вибір останньої $\text{A}$ дає $\text{AAABBB}$. Вибір однієї з $\text{A}$, а потім — $\text{B}$ дає порожній рядок. З іншого боку, якщо спочатку вибрати третю $\text{B}$, отримаємо рядок $\text{ABBAAAAB}$. Можна переконатися, що незалежно від наступних дій отримаємо або рядок $\text{A}$, або рядок $\text{B}$, у яких вже не можна зробити жодного вибору. Тож важливо діяти обережно у виборі послідовності ходів для розв’язання головоломки. Більше того, існують головоломки, які неможливо розв’язати незалежно від вибору. Наприклад, $\text{ABBAAAAB}$ — нерозв’язна головоломка. Відомі певні факти про розв’язні головоломки: порожній рядок — розв’язний. Якщо $x$ і $y$ — розв’язні головоломки, то розв’язними також є $\text{xy}$, $\text{AxA}$ та $\text{AxAyA}$ для будь-якої великої літери $\text{A}$. Усі інші головоломки, не охоплені цими правилами, є нерозв’язними.

За заданою головоломкою визначте, чи можна її розв’язати.