AcWing-175-电路维修

问题

达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。

翰翰的家里有一辆飞行车。

有一天飞行车的电路板突然出现了故障，导致无法启动。

电路板的整体结构是一个 R 行 C 列的网格（R,C≤500），如下图所示。

每个格点都是电线的接点，每个格子都包含一个电子元件。

电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。

在旋转之后，它就可以连接另一条对角线的两个接点。

电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。

达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。

她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。

不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。

注意：只能走斜向的线段，水平和竖直线段不能走。

输入格式

输入文件包含多组测试数据。

第一行包含一个整数 T，表示测试数据的数目。

对于每组测试数据，第一行包含正整数 R 和 C，表示电路板的行数和列数。

之后 R 行，每行 C 个字符，字符是"/"和"\"中的一个，表示标准件的方向。

输出格式

对于每组测试数据，在单独的一行输出一个正整数，表示所需的缩小旋转次数。

如果无论怎样都不能使得电源和发动机之间连通，输出 NO SOLUTION。

数据范围

1≤R,C≤500,
1≤T≤5

输入样例：

1
3 5
\\/\\
\\///
/\\\\

输出样例：

1

样例解释

样例的输入对应于题目描述中的情况。

只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。

思路

• 优先队列bfs

本题每移动一次，花销为 0 或者 1。即为在边权为 0 和 1 的无向图中，给定起点和终点，求起点到终点的最小代价。则此题可以使用优先队列的bfs算法，若当前到达下一个状态的代价为0，则将到达的新状态插入队头，代价为1 则插入队尾。当某节点目状态第一次出队，即为起点到该状态的最小代价，后面此节点再次出队，则忽略。

题解

#include<iostream>
#include<cstring>
#include<cstdio>
#include<deque>

using namespace std;
const int MAX = 505;
char s[MAX][MAX];
int t, r, c, d[MAX][MAX];
int dir[4][2] = {{-1, 1},
                 {1,  1},
                 {1,  -1},
                 {-1, -1}};
bool v[MAX][MAX];
struct P {
    int i, j;
};

// 从p1到p2是否有路径，有返回true，否则false
bool check(P p1, P p2, int d) {
    int x = min(p1.i, p2.i), y = min(p1.j, p2.j);
    if (d == 0 || d == 2) return s[x][y] == '/';
    return s[x][y] == '\\';
}

int main() {
    cin >> t;
    while (t--) {
        cin >> r >> c;
        for (int i = 0; i < r; ++i) scanf("%s", s[i]);
        if ((r + c) & 1) {
            cout << "NO SOLUTION" << endl;
            continue;
        }

        deque<P> q;
        P st = {0, 0};
        memset(v, false, sizeof(v));
        memset(d, 0x3f, sizeof(d));
        v[0][0] = true;
        d[0][0] = 0;
        q.push_back(st);
        while (q.size()) {
            P now = q.front();
            q.pop_front();
            v[now.i][now.j] = true;
            if (now.i == r && now.j == c) {
                cout << d[r][c] << endl;
                break;
            }

            for (int k = 0; k < 4; ++k) {
                int ti = now.i + dir[k][0], tj = now.j + dir[k][1];
                if (ti < 0 || ti > r || tj < 0 || tj > c) continue; //出界
                if (v[ti][tj]) continue;   //访问过

                P nex = {ti, tj};
                if (!check(now, nex, k)) {  //没有通路，步骤加一，放队列后面
                    if (d[ti][tj] > d[now.i][now.j] + 1) {
                        d[ti][tj] = d[now.i][now.j] + 1;
                        q.push_back(nex);
                    }
                } else {
                    if (d[ti][tj] > d[now.i][now.j]) {
                        d[ti][tj] = d[now.i][now.j];
                        q.push_front(nex);   //放队列前面
                    }
                }
            }
        }
    }

    return 0;
}