/*
 * Algorithm / 演算法：
 * 與 C 版本相同：把 grid 視為無向圖，迭代式 BFS + parent 追蹤。
 * Same as the C version: iterative BFS over the implicit undirected graph
 * with parent tracking. Use std::queue and std::array to keep the code
 * idiomatic C++. Time O(m*n), space O(m*n).
 */

#include <vector>
#include <queue>
#include <array>
using namespace std;

class Solution {
public:
    bool containsCycle(vector<vector<char>>& grid) {
        int m = (int)grid.size();              // 列數 / row count
        int n = (int)grid[0].size();           // 行數 / column count

        // 2D bool 陣列，預設皆為 false / 2D visited matrix, default-initialised to false
        vector<vector<bool>> visited(m, vector<bool>(n, false));

        // 四方向位移；用 const 與大括號初始化 / direction deltas, brace-initialized
        const int dr[4] = {-1, 1, 0, 0};
        const int dc[4] = { 0, 0,-1, 1};

        // 對每個 (i,j) 嘗試啟動一次 BFS / launch one BFS per connected component
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j]) continue;   // 已屬於某分量 / already explored

                // std::queue<array<int,4>>：std::array 是固定大小的容器，比 tuple 易讀
                // queue of length-4 int arrays — std::array is a fixed-size container,
                // simpler to read here than std::tuple
                queue<array<int, 4>> q;
                q.push({i, j, -1, -1});         // 推入起點 / enqueue start with sentinel parent
                visited[i][j] = true;           // 入隊立刻標記 / mark on enqueue

                while (!q.empty()) {
                    // structured binding：把 array 拆成 4 個變數，C++17 起支援
                    // Structured binding (C++17) unpacks the array into 4 named variables
                    auto [r, c, pr, pc] = q.front();
                    q.pop();

                    for (int d = 0; d < 4; d++) {
                        int nr = r + dr[d];
                        int nc = c + dc[d];

                        // 邊界檢查 / out-of-bounds guard
                        if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;

                        // 不同字元就不是同色邊 / different letter ⇒ no same-value edge
                        if (grid[nr][nc] != grid[r][c]) continue;

                        // 不能走回 parent / forbidden U-turn
                        if (nr == pr && nc == pc) continue;

                        // 已訪問且不是 parent → 存在另一條路徑回到此格 → 有環
                        // Visited but not the parent ⇒ another route reached it ⇒ cycle
                        if (visited[nr][nc]) return true;

                        visited[nr][nc] = true;       // 標記 / mark before enqueueing
                        q.push({nr, nc, r, c});       // 入隊；當前格成為其 parent / enqueue with current cell as parent
                    }
                }
            }
        }
        return false;                                  // 沒有任何分量含環 / no component contained a cycle
    }
};