/*
 * Algorithm / 演算法:
 *   Treat the grid as a graph: each cell exposes two direction openings based on its street type.
 *   BFS from (0,0); we may step into a neighbor only if both cells' openings face each other.
 *   把網格視為圖，每格依街道類型擁有兩個方向開口；從 (0,0) 做 BFS，
 *   兩格開口互相對應才算連通；若能走到 (m-1, n-1) 即回傳 true。
 */

#include <stdbool.h>
#include <stdlib.h>

bool hasValidPath(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize;                    // 列數 / number of rows
    int n = gridColSize[0];              // 行數 / number of columns (all rows同寬)

    // dirs[t][k] = 第 t 種街道的第 k 個開口方向 (dr, dc)
    // dirs[t][k] = the k-th opening direction (dr, dc) for street type t
    // 索引 0 不使用，留空 / index 0 is unused (street types are 1..6)
    int dirs[7][2][2] = {
        {{0,0},{0,0}},      // 0: 不使用 / unused
        {{0,-1},{0, 1}},    // 1: 左 / left, 右 / right
        {{-1,0},{1, 0}},    // 2: 上 / up,   下 / down
        {{0,-1},{1, 0}},    // 3: 左 / left, 下 / down
        {{0, 1},{1, 0}},    // 4: 右 / right,下 / down
        {{0,-1},{-1,0}},    // 5: 左 / left, 上 / up
        {{0, 1},{-1,0}}     // 6: 右 / right,上 / up
    };

    // visited[r*n + c] 表示 (r,c) 是否已加入佇列 / has (r,c) been enqueued?
    // calloc 會把記憶體初始化為 0 (false) / calloc zero-initializes memory
    bool* visited = (bool*)calloc((size_t)m * n, sizeof(bool));

    // 用陣列模擬 FIFO 佇列，每格存兩個 int (r, c)，最多 m*n 格 / array-backed FIFO queue
    int* queue = (int*)malloc((size_t)m * n * 2 * sizeof(int));
    int head = 0, tail = 0;              // head 取出位置 / pop index, tail 寫入位置 / push index

    queue[tail++] = 0;                   // 推入起點 row / push start row
    queue[tail++] = 0;                   // 推入起點 col / push start col
    visited[0] = true;                   // 標記 (0,0) 已訪問 / mark start visited

    bool found = false;                  // 結果旗標 / result flag
    while (head < tail) {                // 佇列非空 / while queue is non-empty
        int r = queue[head++];           // 取出 row / pop row
        int c = queue[head++];           // 取出 col / pop col

        if (r == m - 1 && c == n - 1) {  // 已到達終點 / reached the bottom-right cell
            found = true;
            break;
        }

        int t = grid[r][c];              // 當前格的街道類型 / current cell's street type
        for (int k = 0; k < 2; k++) {    // 嘗試此街道的兩個開口 / try both openings
            int dr = dirs[t][k][0];      // 方向向量 row 分量 / row delta
            int dc = dirs[t][k][1];      // 方向向量 col 分量 / col delta
            int nr = r + dr;             // 鄰居 row / neighbor row
            int nc = c + dc;             // 鄰居 col / neighbor col

            // 越界則跳過 / skip if out of bounds
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            // 已訪問則跳過，避免無窮迴圈 / skip if visited, prevents revisits
            if (visited[nr * n + nc]) continue;

            int nt = grid[nr][nc];       // 鄰居的街道類型 / neighbor's type
            bool connects = false;       // 雙方是否真的相連 / mutual connection?

            // 鄰居必須有 (-dr, -dc) 方向的開口才算對接成功
            // neighbor must expose the OPPOSITE direction (-dr, -dc) for the link to be valid
            for (int j = 0; j < 2; j++) {
                if (dirs[nt][j][0] == -dr && dirs[nt][j][1] == -dc) {
                    connects = true;
                    break;               // 找到匹配就跳出 / found a match, stop scanning
                }
            }

            if (connects) {              // 雙向連通才入隊 / enqueue only if mutually connected
                visited[nr * n + nc] = true;        // 先標記再入隊 / mark before push
                queue[tail++] = nr;                  // 推入 row / push row
                queue[tail++] = nc;                  // 推入 col / push col
            }
        }
    }

    free(visited);                       // 釋放記憶體避免洩漏 / free to avoid memory leak
    free(queue);                         // 同上 / same
    return found;
}