| Codeforces Round 290 (Div. 2) |
|---|
| Закончено |
Лиса Ciel играет в мобильную игру-головоломку под названием «Две точки». Простейшие уровни играются на доске размера n × m ячеек, выглядящей примерно вот так:
В каждой клетке нарисована точка, обозначенная некоторым цветом. Обозначим различные цвета различными заглавными буквами латинского алфавита.
Задача игрока — найти цикл, состоящий из точек одного цвета. В качестве примера можно рассмотреть обведённые четыре синих точки на картинке. Формально говоря, мы называем последовательность точек d1, d2, ..., dk циклом тогда и только тогда, когда выполняются следующие условия:
- Это k различных точек: если i ≠ j, то di отличается от dj.
- k не менее 4.
- Все точки окрашены в один цвет.
- Для всех 1 ≤ i ≤ k - 1: di и di + 1 смежные. Также, dk и d1 тоже должны быть смежные. Ячейки x и y называются смежными, если у них есть общая сторона.
Определите, есть ли на поле цикл.
В первой строке записано два целых числа, n и m (2 ≤ n, m ≤ 50), количество строк и столбцов доски.
Затем следуют n строк, в каждой строке записана последовательность из m символов, обозначающих цвета точек в этой строке. Каждый символ является заглавной буквой латинского алфавита.
Выведите «Yes», если существует цикл, и «No» в противном случае.
3 4
AAAA
ABCA
AAAA
Yes
3 4
AAAA
ABCA
AADA
No
4 4
YYYR
BYBY
BBBY
BBBY
Yes
7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB
Yes
2 13
ABCDEFGHIJKLM
NOPQRSTUVWXYZ
No
В первом примере буквы 'A' формируют цикл.
Во втором примере цикла не существует.
Третий пример изображён на картинке выше ('Y' обозначает жёлтый, 'B' — синий, 'R' — красный).
