题目传送门

P4667 [BalticOI 2011] Switch the Lamp On 电路维修 (Day1) - 洛谷

思路

题目给出一个 N×M 的网格，每个格子内有一条连接两个对角顶点的电线，电线可能是 / 或 \。电源在左上角格点 (0,0) ，灯在右下角格点 (N,M) 。

我们可以把每个格点看作图上的节点。从一个格点走到相邻的对角格点，一定会穿过一个方格。如果方格里的电线正好连接这两个格点，那么不需要旋转，边权为 0；否则需要把该方格旋转 90∘，边权为 1。

问题就变成了：

从 (0,0) 到 (N,M) 的最短路，边权只有 0 和 1。

因此使用 0-1 BFS 解决。

0-1 BFS 思路

因为边权只有 0 和 1，所以可以用双端队列 deque 代替优先队列。

  • 遇到边权为 0 的边，把目标节点放到队首。

  • 遇到边权为 1 的边，把目标节点放到队尾。

这样队列中的距离始终是单调不减的，每个节点第一次出队时的距离就是最短路。

代码中：

cpp

if (d) dq.push_back(Node{px, py});
else dq.push_front(Node{px, py});

d 为 true 表示需要旋转，边权为 1，放到队尾；
d 为 false 表示不需要旋转，边权为 0，放到队首。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf INT_MAX / 2

//分别对应                 右下，左下，左上，右上
vector<vector<int>> dir({ {1,1},{-1,1},{-1,-1},{1,-1} });//对应的点位
vector<vector<int>> fx({ {0,0},{-1,0},{-1,-1},{0,-1} }); //对应的'/'或者'\'在的位置
vector<char> qd({ '\\', '/', '\\', '/' });               //希望的'/'或者'\'状态
int n, m;

//坐标
struct Node {
    int x, y;
    Node(int _x, int _y) :x(_x), y(_y){}
};

//点位是否在数组范围内，防止数组越界
bool check(int x, int y) {
    if (x < 0) return false;
    if (y < 0) return false;
    if (x > n) return false;
    if (y > m) return false;
    return true;
}

void solve() {
    cin >> n >> m;
    vector<string> edges(n);
    vector<vector<int>> ans(n + 1, vector<int>(m + 1, inf));
    for (int i = 0; i < n; i++) {
        cin >> edges[i];
    }
    deque<Node> dq;
    dq.push_back(Node(0, 0));
    ans[0][0] = 0;
    while (!dq.empty()) {
        Node u = dq.front();
        dq.pop_front();
        int x = u.x;
        int y = u.y;
        //四个方向的遍历
        for (int i = 0; i < 4; i++) {
            int d;
            //防止数组越界
            if (x + fx[i][0] < 0 || y + fx[i][1] < 0 || x + fx[i][0] >= n || y + fx[i][1] >= m) continue;
            //是否需要转向才能到达（x + fx[i][0]， y + fx[i][1]）
            d = (edges[x + fx[i][0]][y + fx[i][1]] != qd[i]);
            int px = x + dir[i][0];
            int py = y + dir[i][1];
            //松弛操作
            if (check(px, py) && ans[px][py] > ans[x][y] + d) {
                ans[px][py] = ans[x][y] + d;
                //如果到达（px，py）不需要反转时就放到队列前面优先判断，否则放后面
                if (d) dq.push_back(Node{ px,py });
                else dq.push_front(Node{ px,py });
            }
        }
    }
    if (ans[n][m] == inf) cout << "NO SOLUTION" << endl;
    else cout << ans[n][m] << endl;
}