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