双端队列

题目描述

给定一个 $n$ 行 $m$ 列的网格，每个格子由字符 \ 或 / 组成，表示电路的连接方向。我们需要从左上角的格点 $(0,0)$ 出发，走到右下角的格点 $(n,m)$。若当前格子的电路方向与移动方向一致，则无需旋转（代价为 $0$）；若不一致，则需要旋转电路（代价为 $1$）。求从起点到终点的最小总代价，若无法到达则输出 NO SOLUTION。

解题思路

1. 奇偶性判断（无解情况）

由于每次移动都是沿对角线方向，格点坐标 $(x,y)$ 的横纵坐标之和 $x+y$ 的奇偶性保持不变。起点 $(0,0)$ 的 $x+y=0$（偶数），若终点 $(n,m)$ 的 $x+y$ 为奇数，则必然无法到达，直接输出 NO SOLUTION。

2. 0-1 BFS 算法

由于边权只有 $0$（无需旋转）和 $1$（需要旋转），我们使用双端队列（deque） 实现高效的最短路算法：

• 若当前移动代价为 $0$，将新节点插入队首（优先处理，保证距离单调性）；
• 若代价为 $1$，将新节点插入队尾。

这种方法的时间复杂度接近线性，比普通 Dijkstra 算法效率更高。

算法分析

• 时间复杂度：$O(nm)$，每个格点最多入队两次，一次从队首，一次从队尾。
• 空间复杂度：$O(nm)$，用于存储距离数组 dis 和网格 g。

代码解释

1. 全局变量

• deque<pair<int, int>> q：双端队列，存储当前处理的格点坐标。
• int dis[N][N]：存储从起点 $(0,0)$ 到每个格点 $(x,y)$ 的最小代价，初始化为 -1（未访问）。
• char g[N][N]：存储网格中的电路方向（/ 或 \）。

2. check 函数

判断格点 $(x,y)$ 是否在合法范围内（$0 \leq x \leq n$，$0 \leq y \leq m$）。

3. push 函数

实现 0-1 BFS 的核心入队逻辑：

• 若当前格点未访问或找到更优路径，则更新距离。
• 若代价为 $0$，插入队首；若代价为 $1$，插入队尾。

代码实现

#include <bits/stdc++.h>
#define endl "\n"
#define N 505
#define ll long long

using namespace std;

deque<pair<int, int>> q; // pair<x, y>，存储格点坐标
int n, m, dis[N][N], t;  // dis[x][y] 表示 (0,0) 到 (x,y) 的最小代价
char g[N][N];             // 存储网格中的电路方向

// 判断格点是否越界
bool check(int x, int y)
{
    return x >= 0 && x <= n && y >= 0 && y <= m;
}

// 双向队列的入队操作
void push(int x, int y, int d)
{
    if (dis[x][y] == -1 || d < dis[x][y])
    {
        dis[x][y] = d;
        // 若队列为空或当前代价大于队首元素代价，插入队尾
        if (q.empty() || d > dis[q.front().first][q.front().second])
            q.push_back({x, y});
        // 否则插入队首
        else
            q.push_front({x, y});
    }
}

void bfs()
{
    memset(dis, -1, sizeof(dis)); // 初始化距离数组为 -1（未访问）
    dis[0][0] = 0;                // 起点距离为 0
    q.push_back({0, 0});          // 起点入队
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop_front();
        // 尝试向四个对角线方向移动
        // 1. 左上移动 (x-1, y-1)
        if (check(x - 1, y - 1))
        {
            if (g[x - 1][y - 1] == '\\')
                push(x - 1, y - 1, dis[x][y]); // 方向一致，代价 0
            else
                push(x - 1, y - 1, dis[x][y] + 1); // 方向不一致，代价 +1
        }
        // 2. 右上移动 (x-1, y+1)
        if (check(x - 1, y + 1))
        {
            if (g[x - 1][y] == '/')
                push(x - 1, y + 1, dis[x][y]);
            else
                push(x - 1, y + 1, dis[x][y] + 1);
        }
        // 3. 左下移动 (x+1, y-1)
        if (check(x + 1, y - 1))
        {
            if (g[x][y - 1] == '/')
                push(x + 1, y - 1, dis[x][y]);
            else
                push(x + 1, y - 1, dis[x][y] + 1);
        }
        // 4. 右下移动 (x+1, y+1)
        if (check(x + 1, y + 1))
        {
            if (g[x][y] == '\\')
                push(x + 1, y + 1, dis[x][y]);
            else
                push(x + 1, y + 1, dis[x][y] + 1);
        }
    }
    printf("%d\n", dis[n][m]); // 输出终点的最小代价
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%s", g[i]);
    // 奇偶性判断：若终点横纵坐标和为奇数，则无解
    if ((n + m) % 2)
    {
        printf("NO SOLUTION\n");
        return 0;
    }
    bfs();
    return 0;
}