题目描述
给定一个 nnn 行 mmm 列的网格，每个格子由字符 \ 或 / 组成，表示电路的连接方向。我们需要从左上角的格点 (0,0)(0,0)(0,0) 出发，走到右下角的格点 (n,m)(n,m)(n,m)。若当前格子的电路方向与移动方向一致，则无需旋转（代价为 000）；若不一致，则需要旋转电路（代价为 111）。求从起点到终点的最小总代价，若无法到达则输出 NO SOLUTION。
解题思路
1. 奇偶性判断（无解情况）
由于每次移动都是沿对角线方向，格点坐标 (x,y)(x,y)(x,y) 的横纵坐标之和 x+yx+yx+y 的奇偶性保持不变。起点 (0,0)(0,0)(0,0) 的 x+y=0x+y=0x+y=0（偶数），若终点 (n,m)(n,m)(n,m) 的 x+yx+yx+y 为奇数，则必然无法到达，直接输出 NO SOLUTION。
2. 0-1 BFS 算法
由于边权只有 000（无需旋转）和 111（需要旋转），我们使用双端队列（deque） 实现高效的最短路算法：
* 若当前移动代价为 000，将新节点插入队首（优先处理，保证距离单调性）；
* 若代价为 111，将新节点插入队尾。
这种方法的时间复杂度接近线性，比普通 Dijkstra 算法效率更高。
算法分析
* 时间复杂度：O(nm)O(nm)O(nm)，每个格点最多入队两次，一次从队首，一次从队尾。
* 空间复杂度：O(nm)O(nm)O(nm)，用于存储距离数组 dis 和网格 g。
代码解释
1. 全局变量
* deque<pair<int, int>> q：双端队列，存储当前处理的格点坐标。
* int dis[N][N]：存储从起点 (0,0)(0,0)(0,0) 到每个格点 (x,y)(x,y)(x,y) 的最小代价，初始化为 -1（未访问）。
* char g[N][N]：存储网格中的电路方向（/ 或 \）。
2. CHECK 函数
判断格点 (x,y)(x,y)(x,y) 是否在合法范围内（0≤x≤n0 \leq x \leq n0≤x≤n，0≤y≤m0 \leq y \leq m0≤y≤m）。
3. PUSH 函数
实现 0-1 BFS 的核心入队逻辑：
* 若当前格点未访问或找到更优路径，则更新距离。
* 若代价为 000，插入队首；若代价为 111，插入队尾。
代码实现
