[BalticOI 2011 Day1] Switch the Lamp On 电路维修

双端队列广搜

#include <bits/stdc++.h>
using namespace std;
int n, m;
char g[505][505];
int idx[505][505]; // 每个格点对应的编号 1~n+1,1~m+1
vector<pair<int, int>> e[501 * 501 + 5];
int dis[501 * 501 + 5];
deque<int> q;
void bfs()
{
    int tot = (n + 1) * (m + 1); // 点 1~tot
    for (int i = 1; i <= tot; i++)
        dis[i] = -1;
    q.push_back(1);
    dis[1] = 0;
    while (!q.empty() && dis[tot] == -1)
    {
        int u = q.front();
        q.pop_front();
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            if (dis[v] == -1 || dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if (w == 0)
                    q.push_front(v);
                else
                    q.push_back(v);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];
    // 格点编号
    for (int i = 1; i <= n + 1; i++)
        for (int j = 1; j <= m + 1; j++)
            idx[i][j] = (i - 1) * (m + 1) + j;
    // 建图
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            int p1 = idx[i][j], p2 = idx[i][j + 1];
            int p3 = idx[i + 1][j], p4 = idx[i + 1][j + 1];
            if (g[i][j] == '\\')
            {
                e[p1].push_back(make_pair(p4, 0));
                e[p4].push_back(make_pair(p1, 0));
                e[p2].push_back(make_pair(p3, 1));
                e[p3].push_back(make_pair(p2, 1));
            }
            else
            {
                e[p1].push_back(make_pair(p4, 1));
                e[p4].push_back(make_pair(p1, 1));
                e[p2].push_back(make_pair(p3, 0));
                e[p3].push_back(make_pair(p2, 0));
            }
        }
    // bfs()
    bfs();
    // 输出
    if (dis[idx[n + 1][m + 1]] == -1)
        cout << "NO SOLUTION";
    else
        cout << dis[idx[n + 1][m + 1]];
    return 0;
}

并查集缩点+广搜

最短路