好的，我们先来分析一下这个题目的思路，然后结合你给出的代码进行详细讲解。

题目理解

我们有一个 $N \times M$ 的网格，每个格子是一个电路元件，有两种状态：

• \（ASCII 92）表示左上到右下有导线
• /（ASCII 47）表示右上到左下有导线

电源在左上角 $(0,0)$，灯泡在右下角 $(N,M)$。

我们可以旋转任意元件 90°（改变导线方向），目标是让电源与灯泡连通，求最少旋转次数。如果无法连通，输出 "NO SOLUTION"。

解题思路

1. 图论建模

将网格的交叉点视为图的节点，坐标 $(i,j)$ 对应节点编号 $(m+1) \times i + j + 1$（因为每行有 $m+1$ 个交叉点）。

每个元件 $(i,j)$ 连接四个交叉点：

• 左上 $(i,j)$
• 右上 $(i,j+1)$
• 左下 $(i+1,j)$
• 右下 $(i+1,j+1)$

2. 边的建立

对于每个元件：

• 如果是 \：
  • 左上↔右下：边权 0（自然连通）
  • 右上↔左下：边权 1（需要旋转一次）
• 如果是 /：
  • 右上↔左下：边权 0（自然连通）
  • 左上↔右下：边权 1（需要旋转一次）

3. 算法选择

虽然题目可以用 0-1 BFS 更高效，但这里使用了 Dijkstra 算法，因为边权只有 0 和 1，Dijkstra 也能正确工作。

代码详细解析

数据结构

struct edge {
    int next, w, v;
} e[1100001];
int head[1100001], d[1100001];

• 使用链式前向星存图
• d[i] 存储从起点到节点 i 的最短距离

节点编号计算

left_up = (m + 1) * i + j + 1;
right_up = (m + 1) * i + j + 2;
left_down = (m + 1) * (i + 1) + j + 1;
right_down = (m + 1) * (i + 1) + j + 2;

• 每个交叉点 $(i,j)$ 对应编号 $(m+1) \times i + j + 1$
• 总节点数：$(n+1) \times (m+1)$

建图逻辑

if (f[j] == 92) { // '\'
    add(left_up, right_down, 0);
    add(right_down, left_up, 0);
    add(left_down, right_up, 1);
    add(right_up, left_down, 1);
}
if (f[j] == 47) { // '/'
    add(left_down, right_up, 0);
    add(right_up, left_down, 0);
    add(left_up, right_down, 1);
    add(right_down, left_up, 1);
}

• 为每个元件添加双向边
• 自然连通：边权 0
• 需要旋转：边权 1

Dijkstra 算法

void Dijkstra() {
    // 初始化
    sum = (m + 1) * (n + 1);  // 总节点数
    for (int i = 1; i <= sum; i++) d[i] = INF;
    
    d[1] = 0;  // 起点编号为1
    priority_queue<node> q;
    q.push({1, d[1]});
    
    while (!q.empty()) {
        node x = q.top(); q.pop();
        if (x.d != d[x.u]) continue;  // 懒惰删除
        
        for (int i = head[x.u]; i; i = e[i].next) {
            int v = e[i].v, w = e[i].w;
            if (d[x.u] + w < d[v]) {
                d[v] = d[x.u] + w;
                q.push({v, d[v]});
            }
        }
    }
    
    // 输出结果
    if (d[sum] == INF) cout << "NO SOLUTION";
    else cout << d[sum];
}

复杂度分析

• 节点数：$(n+1) \times (m+1) \approx 2.5 \times 10^5$（当 $n,m=500$）
• 边数：每个元件产生 4 条双向边，共 $4 \times 2 \times n \times m \approx 2 \times 10^6$
• 时间复杂度：$O(E \log V) \approx 2 \times 10^6 \times \log(2.5 \times 10^5)$，在题目限制内可行

优化建议

1. 使用 0-1 BFS：由于边权只有 0 和 1，可以用双端队列，时间复杂度降为 $O(V+E)$
2. 奇偶性剪枝：如果 $(n+m)$ 是奇数，直接输出 "NO SOLUTION"，因为从 $(0,0)$ 到 $(n,m)$ 的曼哈顿距离奇偶性不匹配

示例验证

对于样例：

3 5
\\/\\
\\///
/\\\\

• 起点：节点 1 $(0,0)$
• 终点：节点 24 $(3,5)$
• 计算得到最短路径权重为 1，输出 1

总结

这个解法将物理的电路连通性问题成功转化为图论最短路径问题，通过合理的建模和经典的 Dijkstra 算法解决了问题。虽然 0-1 BFS 更优，但 Dijkstra 在这个数据规模下仍然可以接受。