1. Идея

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

Разрешены переходы только вверх, вниз, влево и вправо.
Цикл должен иметь длину не меньше 4, то есть нельзя просто сходить из клетки в соседнюю и сразу вернуться.

Классическая идея здесь — поиск цикла в неориентированном графе:

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

Тогда задача сводится к проверке:
есть ли цикл в таком графе?

Для этого удобно использовать DFS (поиск в глубину) с запоминанием клетки, из которой мы пришли.

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

Наблюдение 1. Таблица превращается в граф

Если две соседние клетки содержат одинаковую букву, между ними можно провести ребро.
Так образуются несколько компонент связности — отдельно для букв A, отдельно для B и так далее.

Цикл нужно искать внутри одной такой компоненты.

Наблюдение 2. Это неориентированный граф

Если из клетки (x, y) можно перейти в (nx, ny), то и обратно тоже можно.
Значит, граф неориентированный.

Для поиска цикла в неориентированном графе есть стандартное правило:

• если во время DFS пришли в уже посещённую вершину,
• и это не та вершина, из которой мы только что пришли,

то найден цикл.

Наблюдение 3. Почему нужно помнить родителя

Пусть мы стоим в клетке u, пришли в неё из p.
Среди соседей u обязательно есть p, и он уже посещён. Но это не цикл, а просто обратный переход по тому же ребру.

Поэтому в DFS нужно игнорировать ровно одного соседа — родителя.

Наблюдение 4. Длина цикла автоматически будет не меньше 4

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

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

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

3. Алгоритм

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

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

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

1. Если алгоритм нашёл цикл, то ответ действительно Yes

Предположим, во время DFS из клетки u найден сосед v, который:

• уже посещён;
• не является родителем u;
• имеет ту же букву.

Это означает, что:

• существует путь по дереву DFS от v до u;
• плюс есть ребро u - v.

Объединяя этот путь и ребро u - v, получаем замкнутый путь, то есть цикл.
Все его клетки содержат одну и ту же букву, потому что DFS ходит только по клеткам с одинаковой буквой.

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

2. Если в таблице есть цикл, то алгоритм обязательно его найдёт

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

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

Именно эту ситуацию алгоритм и проверяет.
Следовательно, существующий цикл будет обнаружен, и алгоритм выведет Yes.

3. Полнота перебора

Мы запускаем DFS из каждой ещё не посещённой клетки, значит рассматриваем все компоненты связности.
Поэтому цикл не может остаться незамеченным в какой-либо части поля.

Из пунктов 1–3 следует, что алгоритм корректен.

5. Сложность

Пусть N = n * m — число клеток.

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

• Время: O(n * m)
• Память: O(n * m)

CPP

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

int n, m;
vector<string> g;
vector<vector<int>> vis;
bool found = false;

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

void dfs(int x, int y, int px, int py, char c) {
    vis[x][y] = 1;
    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 (g[nx][ny] != c) continue;

        if (!vis[nx][ny]) {
            dfs(nx, ny, x, y, c);
            if (found) return;
        } else if (!(nx == px && ny == py)) {
            found = true;
            return;
        }
    }
}

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

    cin >> n >> m;
    g.resize(n);
    for (int i = 0; i < n; ++i) cin >> g[i];

    vis.assign(n, vector<int>(m, 0));

    for (int i = 0; i < n && !found; ++i) {
        for (int j = 0; j < m && !found; ++j) {
            if (!vis[i][j]) {
                dfs(i, j, -1, -1, g[i][j]);
            }
        }
    }

    cout << (found ? "Yes" : "No") << '\n';
    return 0;
}

PYTHON

import sys

sys.setrecursionlimit(10**7)

n, m = map(int, sys.stdin.readline().split())
g = [sys.stdin.readline().strip() for _ in range(n)]
vis = [[False] * m for _ in range(n)]
found = False

dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)

def dfs(x, y, px, py, c):
    global found
    vis[x][y] = True
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if g[nx][ny] != c:
            continue
        if not vis[nx][ny]:
            dfs(nx, ny, x, y, c)
            if found:
                return
        elif not (nx == px and ny == py):
            found = True
            return

for i in range(n):
    if found:
        break
    for j in range(m):
        if not vis[i][j]:
            dfs(i, j, -1, -1, g[i][j])
            if found:
                break

print("Yes" if found else "No")