1391. Check if There is a Valid Path in a Grid

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

/*
 * Algorithm / 演算法:
 *   Same idea as the C version: precompute each street type's two opening directions,
 *   then BFS from (0,0), advancing only when both cells' openings face each other.
 *   思路同 C 版：預存六種街道的開口方向，從 (0,0) 做 BFS，
 *   只在「雙向開口對應」時才前進，看能否到達 (m-1, n-1)。
 */

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

class Solution {
public:
    bool hasValidPath(vector<vector<int>>& grid) {
        int m = grid.size();                 // 列數 / rows
        int n = grid[0].size();              // 行數 / cols

        // 每種街道類型的兩個開口方向 / two opening directions per street type
        // 用 vector<vector<pair<int,int>>>，索引 1..6 / indexed 1..6, slot 0 unused
        vector<vector<pair<int,int>>> dirs(7);
        dirs[1] = {{0,-1}, {0, 1}};          // 左右 / left, right
        dirs[2] = {{-1,0}, {1, 0}};          // 上下 / up, down
        dirs[3] = {{0,-1}, {1, 0}};          // 左下 / left, down
        dirs[4] = {{0, 1}, {1, 0}};          // 右下 / right, down
        dirs[5] = {{0,-1}, {-1,0}};          // 左上 / left, up
        dirs[6] = {{0, 1}, {-1,0}};          // 右上 / right, up

        // 訪問標記，避免重複入隊 / visited matrix
        vector<vector<bool>> visited(m, vector<bool>(n, false));

        // std::queue 是 FIFO 容器，push 加到尾端，front/pop 從前端取出
        // std::queue is a FIFO; push() appends, front()/pop() retrieve and remove
        queue<pair<int,int>> q;
        q.push({0, 0});                      // 起點入隊 / enqueue start
        visited[0][0] = true;

        while (!q.empty()) {
            // C++17 結構化綁定，把 pair 拆成 r, c 兩個名字
            // C++17 structured bindings: split a pair into two named variables
            auto [r, c] = q.front();
            q.pop();

            if (r == m - 1 && c == n - 1) return true;   // 已抵達終點 / target reached

            int t = grid[r][c];               // 當前街道類型 / current street type
            // range-for 走訪 dirs[t] 中的兩個方向 / iterate the two openings
            for (auto [dr, dc] : dirs[t]) {
                int nr = r + dr;              // 鄰居 row / neighbor row
                int nc = c + dc;              // 鄰居 col / neighbor col
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;  // 越界 / OOB
                if (visited[nr][nc]) continue;                          // 已訪問 / seen

                int nt = grid[nr][nc];        // 鄰居街道類型 / neighbor type
                bool connects = false;        // 雙向是否連通 / mutual link?

                // 鄰居必須有反方向 (-dr, -dc) 的開口 / neighbor needs the opposite opening
                for (auto [ddr, ddc] : dirs[nt]) {
                    if (ddr == -dr && ddc == -dc) {
                        connects = true;
                        break;
                    }
                }

                if (connects) {
                    visited[nr][nc] = true;   // 先標記再入隊，防重複 / mark before push
                    q.push({nr, nc});         // 入隊 / enqueue neighbor
                }
            }
        }

        return false;                         // 終點不可達 / target unreachable
    }
};