Мозаика светящихся плит

Просмотр в формате PDF

Submit solution


Очки: 140
Ограничение по времени: 1.0s
Ограничение по памяти: 64M

Автор:
Problem types
Allowed languages
C++, Python

В магическом дворце находится прямоугольный зал, пол которого выложен светящимися плитами. Каждая плита имеет один из нескольких цветов, обозначенных заглавной латинской буквой.

Две плиты считаются соседними, если у них есть общая сторона. Колдун хочет узнать, существует ли в мозаике замкнутый магический узор — цикл из плит одного цвета.

Формально, требуется определить, можно ли выбрать последовательность различных плит одного и того же цвета
$ 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

Комментарии

Еще нет ни одного комментария.