/*
 * Algorithm / 演算法：
 * 把同字元相鄰格子視為無向圖的邊，做 iterative BFS 並記錄 parent。
 * Treat same-letter adjacencies as edges of an undirected graph; run BFS
 * with parent tracking. If we ever reach an already-visited neighbor that
 * is not our parent, the graph contains a cycle. Time O(m*n), space O(m*n).
 */

#include <stdbool.h>   // bool 型別 / brings in `bool`, `true`, `false`
#include <stdlib.h>    // malloc / calloc / free

bool containsCycle(char** grid, int gridSize, int* gridColSize) {
    int m = gridSize;              // 列數 / number of rows
    int n = gridColSize[0];        // 行數（每列同寬） / columns (rows are same width)

    // visited[i*n + j] = true 表示 (i,j) 已經被某次 BFS 走過
    // visited[i*n + j] is true once cell (i,j) has been enqueued
    bool* visited = (bool*)calloc((size_t)m * n, sizeof(bool));

    // queue 用一塊大陣列模擬，每格存 4 個 int：r, c, parentR, parentC
    // We back the BFS queue with one big int array; each slot stores
    // (r, c, pr, pc). 4 * m * n is the worst-case capacity (each cell once).
    int* queue = (int*)malloc((size_t)m * n * 4 * sizeof(int));

    // 四個方向的位移：上、下、左、右
    // Direction deltas for up/down/left/right neighbors
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = { 0, 0,-1, 1};

    bool result = false;           // 找到環就設為 true / set true once a cycle is found

    // 雙層迴圈嘗試從每一個尚未拜訪的格子啟動一次 BFS（每個連通分量一次）
    // Outer loops launch a BFS from each unvisited cell — one per component
    for (int i = 0; i < m && !result; i++) {
        for (int j = 0; j < n && !result; j++) {
            if (visited[i * n + j]) continue; // 已屬於某個分量 / belongs to a component already

            int head = 0, tail = 0;          // queue 的前後指標 / BFS queue pointers
            // 把起點推進 queue：parent 用 (-1,-1) 代表「沒有上一步」
            // Push the start with sentinel parent (-1,-1) meaning "no previous step"
            queue[tail * 4 + 0] = i;
            queue[tail * 4 + 1] = j;
            queue[tail * 4 + 2] = -1;
            queue[tail * 4 + 3] = -1;
            tail++;
            visited[i * n + j] = true;       // 入隊就立刻標記 / mark on enqueue

            while (head < tail && !result) {
                // 取出隊首 / dequeue front
                int r  = queue[head * 4 + 0];
                int c  = queue[head * 4 + 1];
                int pr = queue[head * 4 + 2]; // parent row
                int pc = queue[head * 4 + 3]; // parent col
                head++;

                // 嘗試四個方向的鄰居 / try all four neighbors
                for (int d = 0; d < 4; d++) {
                    int nr = r + dr[d];      // neighbor 的 row
                    int nc = c + dc[d];      // neighbor 的 col

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

                    // 字元不同 → 不算同色邊 / different letter, no edge
                    if (grid[nr][nc] != grid[r][c]) continue;

                    // 不能立刻走回 parent / cannot step back to where we came from
                    if (nr == pr && nc == pc) continue;

                    // 已訪問且不是 parent ⇒ 找到另一條路徑回到此格 ⇒ 有環
                    // Already visited and not the parent ⇒ alternate path ⇒ cycle
                    if (visited[nr * n + nc]) {
                        result = true;
                        break;
                    }

                    // 否則：標記、入隊，把當前 (r,c) 當作新格的 parent
                    // Otherwise: mark, enqueue, recording (r,c) as the new cell's parent
                    visited[nr * n + nc] = true;
                    queue[tail * 4 + 0] = nr;
                    queue[tail * 4 + 1] = nc;
                    queue[tail * 4 + 2] = r;
                    queue[tail * 4 + 3] = c;
                    tail++;
                }
            }
        }
    }

    free(visited);   // 釋放堆積記憶體 / free heap memory
    free(queue);
    return result;
}