1. Идея

Нужно проверить, есть ли в прямоугольной сетке цикл, состоящий только из плит одного цвета.

Это удобно рассматривать как граф:

• каждая клетка — вершина;
• между двумя вершинами есть ребро, если клетки соседние по стороне и имеют одинаковый цвет.

Тогда задача сводится к поиску цикла в неориентированном графе.

Для этого запускаем обход в глубину по всем клеткам.
Если из текущей клетки можно перейти в уже посещённую клетку того же цвета, и эта клетка не является родителем в обходе, значит найден цикл.

Именно эту идею реализует эталонное решение: итеративный DFS со стеком.

2. Наблюдения

Наблюдение 1. Цикл ищется отдельно внутри клеток одного цвета

Переходить можно только между соседними клетками одинакового цвета.
Значит, клетки разных цветов никак не участвуют в одном и том же узоре.

Поэтому при запуске обхода из клетки с цветом ch мы фактически исследуем только связанную компоненту этого цвета.

Наблюдение 2. В неориентированном графе цикл обнаруживается через возврат в уже посещённую вершину

Во время DFS у каждой вершины есть родитель — клетка, из которой мы в неё пришли.

Если из клетки (x, y) мы видим соседнюю клетку (nx, ny):

• если она ещё не посещена, продолжаем обход;
• если она уже посещена и это не родитель текущей клетки, то найден цикл.

Почему нужно исключать родителя?
Потому что в неориентированном графе каждое ребро видно с двух сторон. Возврат назад по тому же ребру не означает цикл.

Наблюдение 3. Условие про длину не менее 4 отдельно проверять не нужно

В обычной прямоугольной сетке с соседством по стороне невозможно получить цикл длины 2 или 3:

• длина 2 невозможна, потому что между двумя клетками только одно ребро;
• длина 3 невозможна, потому что в такой сетке нет треугольников.

Поэтому если DFS обнаружил цикл, он автоматически имеет длину хотя бы 4, как и требуется в условии.

3. Алгоритм

1. Считываем n, m и саму таблицу grid.
2. Создаём массив vis, где vis[x][y] = 1, если клетка уже посещена.
3. Проходим по всем клеткам (sx, sy):
   • если клетка уже посещена, пропускаем;
   • иначе начинаем из неё DFS.
4. В стек кладём состояние из четырёх чисел:
   • текущая клетка (x, y);
   • родительская клетка (px, py).
5. Пока стек не пуст:
   • достаём вершину;
   • перебираем 4 соседних направления;
   • для соседа (nx, ny):
     • проверяем границы;
     • проверяем, что цвет совпадает с цветом стартовой компоненты;
     • если сосед не посещён, помечаем его и кладём в стек;
     • если сосед уже посещён и это не родитель, выводим Yes.
6. Если все компоненты обработаны и цикл не найден, выводим No.

4. Почему это работает

Докажем корректность алгоритма.

1. Алгоритм не пропустит существующий цикл

Рассмотрим любую компоненту связности клеток одного цвета.
Алгоритм обязательно запустит DFS из одной из клеток этой компоненты, если она ещё не была посещена ранее, и обойдёт всю компоненту.

Если в компоненте есть цикл, то при DFS рано или поздно встретится ситуация, когда из текущей вершины можно пройти в уже посещённую вершину, которая не является родителем. Это стандартный признак цикла в неориентированном графе.

Значит, если цикл существует, алгоритм обнаружит его и выведет Yes.

2. Если алгоритм вывел Yes, цикл действительно существует

Алгоритм выводит Yes только тогда, когда из клетки (x, y) найден сосед (nx, ny):

• того же цвета,
• уже посещённый,
• не совпадающий с родителем (px, py).

Так как обход идёт только по клеткам одного цвета, найденное ребро соединяет вершины внутри одной и той же компоненты этого цвета.

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

3. Почему условие задачи выполняется полностью

Найденный цикл состоит:

• из соседних по стороне клеток;
• все клетки имеют одинаковый цвет;
• цикл в такой сетке имеет длину не менее 4.

То есть найденная структура полностью соответствует определению из условия.

Следовательно, алгоритм корректен.

5. Сложность

Пусть всего клеток n * m.

Каждая клетка посещается не более одного раза, и для каждой клетки проверяются 4 соседа.

Итоговая сложность:

• по времени: O(n * m)
• по памяти: O(n * m)

При ограничениях n, m <= 50 это работает очень быстро.

6. Код на C++17

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; ++i) cin >> grid[i];

    vector<vector<int>> vis(n, vector<int>(m, 0));
    const int dx[4] = {-1, 1, 0, 0};
    const int dy[4] = {0, 0, -1, 1};

    for (int sx = 0; sx < n; ++sx) {
        for (int sy = 0; sy < m; ++sy) {
            if (vis[sx][sy]) continue;

            char ch = grid[sx][sy];
            stack<array<int, 4>> st;
            st.push({sx, sy, -1, -1});
            vis[sx][sy] = 1;

            while (!st.empty()) {
                auto cur = st.top();
                st.pop();

                int x = cur[0], y = cur[1];
                int px = cur[2], py = cur[3];

                for (int dir = 0; dir < 4; ++dir) {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];

                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if (grid[nx][ny] != ch) continue;

                    if (!vis[nx][ny]) {
                        vis[nx][ny] = 1;
                        st.push({nx, ny, x, y});
                    } else if (!(nx == px && ny == py)) {
                        cout << "Yes\n";
                        return 0;
                    }
                }
            }
        }
    }

    cout << "No\n";
    return 0;
}

7. Код на Python 3

import sys

def solve():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    grid = [input().strip() for _ in range(n)]

    vis = [[0] * m for _ in range(n)]
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    for sx in range(n):
        for sy in range(m):
            if vis[sx][sy]:
                continue

            ch = grid[sx][sy]
            stack = [(sx, sy, -1, -1)]
            vis[sx][sy] = 1

            while stack:
                x, y, px, py = stack.pop()

                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if not (0 <= nx < n and 0 <= ny < m):
                        continue
                    if grid[nx][ny] != ch:
                        continue

                    if not vis[nx][ny]:
                        vis[nx][ny] = 1
                        stack.append((nx, ny, x, y))
                    elif not (nx == px and ny == py):
                        print("Yes")
                        return

    print("No")

if __name__ == "__main__":
    solve()