【百题千解】题解 P2243 【电路维修】

思路引导

我们可以把电路板上的每个格点 (横线与竖线的交叉点) 看作无向图的结点。若两个顶点 x 和 y 之间的连边。若该方格中的标准件(对角线)与 x 到 y 的线段重合，则边权为 0 ；若垂直相交，则边权为 1 (说明需要旋转 1 次才能连通 )。然后，我们在这个无向图中求出从左上角到右下角的最短距离，就得到了结果。

这是一个边权要么是 0，要么是 1 的无向图。在这样的图上，我们可以通过双端队列广度搜索来计算。算法的整体框架与一般的广度搜索类似，只是在每个节点上沿分支扩展时稍作改变。如果这条分支是边权为 0 的边，就把沿该分支到达的新节点从队头入队；如果这条分支是边权为 1 的边，就像一般的广度搜索一样从队尾入队。这样一来，我们就仍能保证任意时刻广度搜索队列中的结点对应的距离值都具有“两段性”和“单调性”，每个结点从队头出队时，就能得到左上角到该节点的最短距离。

因为每个结点只需要访问一次，所以算法的时间复杂度为 O (R×C）。

代码解释

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int cap = 500010;
int dist[510][510]; char map[510][510]; bool proc[510][510];
pair<int, int>queue[cap * 2]; int r, c, li, ri;
inline bool valid(int x, int y)
{
    return x >= 0 && x <= r && y >= 0 && y <= c;
}
inline void que_add(int x, int y, int v)
{
    if (dist[x][y] < 0 || v < dist[x][y]) {
        dist[x][y] = v;
        if (li == ri || v > dist[queue[li].first][queue[li].second]) queue[ri++] = make_pair(x, y);
        else queue[--li] = make_pair(x, y);
    }
}
signed main()
{
    int kase;

    for (scanf("%d", &kase); kase; --kase) {
        scanf("%d %d", &r, &c);
        if ((r + c) % 2) {
            for (int i = 0; i < r; i++) scanf("%s", map[i]);
            printf("NO SOLUTION\n");
        }else {
            for (int i = 0; i < r; i++) scanf("%s", map[i]);
            li = ri = cap; queue[ri++] = make_pair(0, 0);
            memset(dist, -1, sizeof dist), dist[0][0] = 0;
            memset(proc, false, sizeof proc);
            while (li != ri) {
                int cx = queue[li].first, cy = queue[li].second; ++li;
                if (valid(cx - 1, cy + 1)) {
                    if (map[cx - 1][cy - 1] == '\\') que_add(cx - 1, cy - 1, dist[cx][cy]);
                    else que_add(cx - 1, cy - 1, dist[cx][cy] + 1);
                }
                if (valid(cx - 1, cy + 1)) {
                    if (map[cx - 1][cy] == '/') que_add(cx - 1, cy + 1, dist[cx][cy]);
                    else que_add(cx - 1, cy + 1, dist[cx][cy] + 1);
                }
                if (valid(cx + 1, cy - 1)) {
                    if (map[cx][cy - 1] == '/') que_add(cx + 1, cy - 1, dist[cx][cy]);
                    else que_add(cx + 1, cy - 1, dist[cx][cy] + 1);
                }
                if (valid(cx + 1, cy + 1)) {
                    if (map[cx][cy] == '\\') que_add(cx + 1, cy + 1, dist[cx][cy]);
                    else que_add(cx + 1, cy + 1, dist[cx][cy] + 1);
                }
            }
            printf("%d\n", dist[r][c]);
        }
    }
    return 0;
}

建议 50 分的同学可以参考一下本题解 @Sxy_Limit