Мозаика светящихся плит
Просмотр в формате PDFВ магическом дворце находится прямоугольный зал, пол которого выложен светящимися плитами. Каждая плита имеет один из нескольких цветов, обозначенных заглавной латинской буквой.
Две плиты считаются соседними, если у них есть общая сторона. Колдун хочет узнать, существует ли в мозаике замкнутый магический узор — цикл из плит одного цвета.
Формально, требуется определить, можно ли выбрать последовательность различных плит одного и того же цвета
$ p_1, p_2, \dots, p_k $ так, что:
- $ k \ge 4 $;
- каждые две соседние в последовательности плиты имеют общую сторону, то есть $ p_i $ соседствует с $ p_{i+1} $ для всех $ 1 \le i < k $;
- последняя плита $ p_k $ соседствует с первой $ p_1 $.
Иными словами, нужно проверить, существует ли цикл длины не меньше 4, состоящий только из плит одного цвета.
Входные данные
В первой строке заданы два целых числа $ n $ и $ m $ — количество строк и столбцов в мозаике.
В следующих $ n $ строках содержится описание зала: по строке длины $ m $, состоящей из заглавных латинских букв.
Символ в $ j $-й позиции $ i $-й строки обозначает цвет плиты в клетке $ (i, j) $.
Выходные данные
Выведите:
Yes, если в мозаике существует замкнутый магический узор;Noв противном случае.
Ограничения
- $ 2 \le n, m \le 50 $
- Каждая клетка содержит заглавную латинскую букву английского алфавита.
Примеры
Пример 1
Входные данные
3 4
AAAA
ABCA
AADA
Выходные данные
Yes
Пример 2
Входные данные
3 4
AAAA
ABCA
AADA
Выходные данные
Yes
Пример 3
Входные данные
4 4
YYYR
BYBY
BBBY
BBBY
Выходные данные
No
Комментарии