题解：机器人网格移动（最小转弯次数问题）

核心结论：将机器人的“位置+方向”视为状态，通过 BFS 预处理特殊格之间的转移关系，查询时结合起点/终点的直线可达性与预处理结果，高效计算最小转弯次数。

一、核心思路（通俗版）

1. 问题本质：机器人沿方向直线移动，仅在特殊格（L/R）或到达目标时转弯，求从起点到终点的最少转弯次数。
2. 关键观察：
   • 直线移动特性：无特殊格时，机器人沿方向无限循环移动（网格翻折），若起点和终点在同一直线上，转弯次数为 0。
   • 特殊格的作用：仅特殊格能改变移动方向，转弯次数仅由“经过的特殊格数量”决定（每经过一个特殊格最多转 1 次弯）。
   • 状态简化：无需遍历所有网格（n,m 达 1e6），仅关注“特殊格+起点+终点”，因为普通格不影响方向。
3. 核心模型：将每个“特殊格+进入方向”作为状态，预处理状态间的转移（直线移动到下一个特殊格的转弯次数），查询时通过 BFS 结合预处理结果求解。

二、关键预处理（O(k log k)）

1. 数据结构存储特殊格

• 用哈希表/字典存储特殊格：grid[(x,y)] = s（s 为 L 或 R），支持 O(1) 查询某个位置是否为特殊格。
• 按行、列分组存储特殊格：
  • 行分组：row[x] 存储第 x 行所有特殊格的列坐标（排序）。
  • 列分组：col[y] 存储第 y 列所有特殊格的行坐标（排序）。 目的是快速找到“某方向上距离当前位置最近的特殊格”。

2. 方向定义与转弯规则

• 方向编码：上（0）、右（1）、下（2）、左（3）（顺时针顺序）。
• 转弯规则：
  • 左转（L）：方向 = (dir - 1) % 4（如右→上）。
  • 右转（R）：方向 = (dir + 1) % 4（如右→下）。
• 翻折坐标计算：沿方向移动时，超出网格边界后翻折到对侧，公式如下： | 方向 | 移动方式 | 翻折后坐标（超出时） | |------|-------------------------|-------------------------------| | 上 | 行 x 减 1 | x = n - ( (1 - x) % n ) % n | | 下 | 行 x 加 1 | x = (x - 1) % n + 1 | | 左 | 列 y 减 1 | y = m - ( (1 - y) % m ) % m | | 右 | 列 y 加 1 | y = (y - 1) % m + 1 |

3. 预处理特殊格间的转移

• 状态定义：(x, y, dir) 表示机器人在特殊格 (x,y)，且即将沿 dir 方向移动（进入特殊格后已完成转弯）。
• 转移计算：对每个状态，沿 dir 方向直线移动，找到下一个特殊格（或检测无限循环）：
  1. 沿 dir 方向遍历，利用行/列分组的排序数组，通过二分查找快速定位最近的特殊格。
  2. 若移动过程中经过终点（查询时动态判断），则当前转弯次数有效。
  3. 若到达下一个特殊格 (nx, ny)，则新状态为 (nx, ny, new_dir)，转弯次数 +1（new_dir 由特殊格类型决定）。
• 预处理结果：存储每个状态到其他状态的最小转弯次数（用 BFS 预处理，因转弯次数是分层的）。

三、查询处理（O(1) 直线判断 + O(BFS 层数) 转移查询）

1. 第一步：判断起点和终点是否相同

若 (a_i, b_i) == (c_i, d_i)，输出 0。

2. 第二步：判断直线可达（转弯次数 0）

• 检查起点和终点是否在同一直线上（同行、同列，或沿方向移动时翻折后可达）。
• 沿 4 个方向分别模拟：从起点出发，沿方向直线移动（不考虑特殊格，因起点/终点若为特殊格则失效），若能到达终点，输出 0。

3. 第三步：利用预处理转移求解（转弯次数 ≥1）

• 收集所有可能的“起点→第一个特殊格”的状态：
  1. 从起点出发，沿 4 个方向移动，找到每个方向上的第一个特殊格 (x, y)。
  2. 计算到达 (x, y) 时的转弯次数（0，因未经过其他特殊格），状态为 (x, y, new_dir)（new_dir 由 (x,y) 的特殊类型决定）。
• 收集所有可能的“最后一个特殊格→终点”的状态：
  1. 从终点出发，沿 4 个方向反向移动（即从终点向 dir 方向的反方向移动），找到每个方向上的第一个特殊格 (x, y)。
  2. 该特殊格的状态 (x, y, dir) 能直线到达终点（转弯次数 0）。
• BFS 求解：以“起点→第一个特殊格”的状态为起点，以“能到达终点的特殊格状态”为目标，查询最小转弯次数（预处理的转移次数 + 1？需结合实际转移）。

4. 第四步：处理特殊情况

• 无特殊格（k=0）：仅当直线可达时输出 0，否则输出 -1。
• 无法到达：BFS 后未找到目标状态，输出 -1。

四、核心算法优化

1. 直线可达性快速判断

• 同行判断：x1 == x2，且沿左右方向移动时，翻折后能到达 y2。
• 同列判断：y1 == y2，且沿上下方向移动时，翻折后能到达 x2。
• 公式简化：以右方向为例，从 (x, y1) 到 (x, y2) 的条件是 (y2 - y1) ≡ t * m (mod m)（t 为移动步数），且中途无特殊格（或特殊格为起点/终点，失效）。

2. 特殊格转移的二分查找优化

• 沿某方向找下一个特殊格时，利用排序后的行/列数组，通过二分查找快速定位：
  • 右方向：在 row[x] 中找大于 y 的最小列坐标。
  • 左方向：在 row[x] 中找小于 y 的最大列坐标。
  • 上/下方向同理，在 col[y] 中查找。
• 翻折情况处理：若当前方向无特殊格，则翻折后继续查找（等价于在排序数组中循环查找）。

3. BFS 分层处理

• 预处理时，对所有特殊格状态进行 BFS，按转弯次数分层，存储每个状态的最小转弯次数，查询时直接复用。
• 因 k ≤ 1e5，每个特殊格有 4 个方向，总状态数为 4e5，BFS 复杂度 O(4e5)，可接受。

五、样例解析（样例 1）

输入

2 2 2，特殊格 (1,1,L)、(2,2,R)，查询 (2,1)→(1,2)。

分析

1. 起点 (2,1)，终点 (1,2)，不同行不同列，直线不可达。
2. 起点沿“上”方向移动：翻折后到达 (1,1)（特殊格，起点不是特殊格，生效）。
3. (1,1) 是 L 格，左转（上→左），转弯次数 +1。
4. 沿左方向移动：翻折后到达 (1,2)（终点），总转弯次数 1，输出 1。

六、复杂度分析

• 预处理：O(k log k)（排序行/列特殊格）+ O(4k)（BFS 预处理状态转移）。
• 查询：O(1)（直线判断）+ O(4)（起点到特殊格）+ O(4)（特殊格到终点）+ O(1)（查询预处理结果），总 O(1) 每查询，适配 q ≤ 3e5。
• 空间复杂度：O(k)（存储特殊格和状态转移），可接受。

七、代码框架（核心逻辑）

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXK = 1e5 + 5;
const int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上、右、下、左
unordered_map<ll, char> grid; // 存储特殊格，key = x * (1e9+7) + y
unordered_map<int, vector<int>> row_spec, col_spec; // 行/列分组的特殊格坐标（排序）
int n, m, k, q;

// 坐标哈希：(x,y) → 唯一值
ll hash_pos(int x, int y) {
    return 1LL * x * (1e9 + 7) + y;
}

// 检查 (x1,y1) 沿 dir 方向是否能直线到达 (x2,y2)（忽略特殊格，或特殊格为起点/终点）
bool is_straight(int x1, int y1, int x2, int y2, int dir) {
    if (x1 == x2 && y1 == y2) return true;
    int dx = dirs[dir][0], dy = dirs[dir][1];
    // 模拟翻折移动，判断是否能到达
    // 简化逻辑：同行/同列且翻折后距离一致
    if (dx != 0) { // 上下方向（同列）
        if (y1 != y2) return false;
        int len = abs(x2 - x1);
        return len % n == 0; // 翻折后可达
    } else { // 左右方向（同行）
        if (x1 != x2) return false;
        int len = abs(y2 - y1);
        return len % m == 0;
    }
}

// 从 (x,y) 沿 dir 方向找下一个特殊格，返回 (nx, ny, 距离是否合法)
tuple<int, int, bool> find_next_spec(int x, int y, int dir) {
    int dx = dirs[dir][0], dy = dirs[dir][1];
    if (dx != 0) { // 上下方向（列 y 固定）
        auto it = col_spec.find(y);
        if (it == col_spec.end()) return {-1, -1, false};
        auto &cols = it->second;
        if (dx == -1) { // 上：找小于 x 的最大行
            auto pos = upper_bound(cols.begin(), cols.end(), x);
            if (pos != cols.begin()) {
                pos--;
                return {*pos, y, true};
            } else { // 翻折，找最大行
                return {cols.back(), y, true};
            }
        } else { // 下：找大于 x 的最小行
            auto pos = lower_bound(cols.begin(), cols.end(), x);
            if (pos != cols.end()) {
                return {*pos, y, true};
            } else { // 翻折，找最小行
                return {cols[0], y, true};
            }
        }
    } else { // 左右方向（行 x 固定）
        auto it = row_spec.find(x);
        if (it == row_spec.end()) return {-1, -1, false};
        auto &rows = it->second;
        if (dy == 1) { // 右：找大于 y 的最小列
            auto pos = lower_bound(rows.begin(), rows.end(), y);
            if (pos != rows.end()) {
                return {x, *pos, true};
            } else { // 翻折，找最小列
                return {x, rows[0], true};
            }
        } else { // 左：找小于 y 的最大列
            auto pos = upper_bound(rows.begin(), rows.end(), y);
            if (pos != rows.begin()) {
                pos--;
                return {x, *pos, true};
            } else { // 翻折，找最大列
                return {x, rows.back(), true};
            }
        }
    }
}

// 预处理特殊格间的转移：dist[(x,y,dir)] = 最小转弯次数
unordered_map<ll, int> dist;
void preprocess() {
    queue<tuple<int, int, int>> q;
    // 初始化所有特殊格的 4 个方向状态
    for (auto &[pos, s] : grid) {
        int x = pos / (1e9 + 7), y = pos % (1e9 + 7);
        for (int dir = 0; dir < 4; dir++) {
            ll state = hash_pos(x, y) * 4 + dir;
            dist[state] = 0;
            q.emplace(x, y, dir);
        }
    }
    // BFS 预处理转移
    while (!q.empty()) {
        auto [x, y, dir] = q.front();
        q.pop();
        ll curr_state = hash_pos(x, y) * 4 + dir;
        // 沿 dir 方向找下一个特殊格
        auto [nx, ny, ok] = find_next_spec(x, y, dir);
        if (!ok) continue;
        // 计算下一个方向（根据特殊格类型）
        char s = grid[hash_pos(nx, ny)];
        int new_dir;
        if (s == 'L') new_dir = (dir - 1 + 4) % 4;
        else new_dir = (dir + 1) % 4;
        // 新状态
        ll new_state = hash_pos(nx, ny) * 4 + new_dir;
        if (dist.count(new_state) == 0 || dist[new_state] > dist[curr_state] + 1) {
            dist[new_state] = dist[curr_state] + 1;
            q.emplace(nx, ny, new_dir);
        }
    }
}

int solve_query(int a, int b, int c, int d) {
    // 情况 1：起点 == 终点
    if (a == c && b == d) return 0;
    // 情况 2：直线可达（转弯次数 0）
    for (int dir = 0; dir < 4; dir++) {
        if (is_straight(a, b, c, d, dir)) {
            return 0;
        }
    }
    // 情况 3：无特殊格，无法到达
    if (k == 0) return -1;
    // 情况 4：通过特殊格转移
    int min_turn = INT_MAX;
    // 收集起点→第一个特殊格的状态（转弯次数 0）
    vector<tuple<int, int, int>> start_states;
    for (int dir = 0; dir < 4; dir++) {
        auto [nx, ny, ok] = find_next_spec(a, b, dir);
        if (!ok) continue;
        // 检查从起点到 (nx, ny) 的路径是否经过终点（若经过则转弯次数 0，已在情况 2 处理）
        char s = grid[hash_pos(nx, ny)];
        int new_dir = (s == 'L') ? (dir - 1 + 4) % 4 : (dir + 1) % 4;
        start_states.emplace_back(nx, ny, new_dir);
    }
    // 收集能到达终点的特殊格状态（转弯次数 0）
    unordered_set<ll> end_states;
    for (int dir = 0; dir < 4; dir++) {
        // 反向方向：从终点向 dir 方向移动，等价于从特殊格向 dir 方向移动到终点
        int rev_dir = (dir + 2) % 4;
        auto [nx, ny, ok] = find_next_spec(c, d, rev_dir);
        if (!ok) continue;
        ll state = hash_pos(nx, ny) * 4 + dir;
        end_states.insert(state);
    }
    // 计算最小转弯次数
    for (auto [x, y, dir] : start_states) {
        ll state = hash_pos(x, y) * 4 + dir;
        if (end_states.count(state)) {
            min_turn = min(min_turn, 1); // 起点→特殊格（0 转）+ 特殊格→终点（0 转），总 1 转