1559. Detect Cycles in 2D Grid

grid = [["a","a","a","a"],
        ["a","b","b","a"],
        ["a","b","b","a"],
        ["a","a","a","a"]]
Output: true

/*
 * 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;
}

/*
 * 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
    }
};