题目
175. 电路维修 - AcWing题库 达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。
翰翰的家里有一辆飞行车。
有一天飞行车的电路板突然出现了故障，导致无法启动。
电路板的整体结构是一个 行 列的网格（，如下图所示。
1
每个格点都是电线的接点，每个格子都包含一个电子元件。
电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。
在旋转之后，它就可以连接另一条对角线的两个接点。
电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。
达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。
她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。
不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。
注意：只能走斜向的线段，水平和竖直线段不能走。
输入格式
输入文件包含多组测试数据。
第一行包含一个整数 ，表示测试数据的数目。
对于每组测试数据，第一行包含正整数 和 ，表示电路板的行数和列数。
之后 行，每行 个字符，字符是"/"和"\"中的一个，表示标准件的方向。
输出格式
对于每组测试数据，在单独的一行输出一个正整数，表示所需的最小旋转次数。
如果无论怎样都不能使得电源和发动机之间连通，输出 NO SOLUTION。
数据范围
,
输入样例：
1
3 5
\\/\\
\\///
/\\\\输出样例：
1样例解释
样例的输入对应于题目描述中的情况。
只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。
1
思路
该题和之前2022CCPC的水管题几乎一样, ε=(´ο｀*)))唉。
从一个点走到相邻的另一个点有两种情况, 不旋转, 旋转, 这两条边的边权分别为0, 1。 故我们要求的就是从起点到终点的一个无向图最短路问题。
求之前需要先找出所有不可能抵达的点, 避免在计算路径时把他们的权值也算上。 这里的话简单枚举可以归纳出来就是坐标和为偶数的节点都是不可抵达的节点。
只包含01边权的最短路可以用双端队列来做。 双端队列就是把扩展队头元素所得到的元素, 本来是要统一插到队尾, 这里加个判断, 若边权为0则插到队头, 若边权为1则插到队尾。其余都和BFS一样。
扩展队头时需要确认两点：
- 扩展点的坐标
- 该路径的权值
1
显然对于点(1,2)只能通过斜着走到其他点, 故dx,dy为：
// 左上 右上 左下 右下
dx[] = {-1,-1,1,1};
dy[] = {-1,1,-1,1};而从一个点走到另一个点时, 还需要判断两点之间的线是否需要旋转, 这里用ix, iy计算出两点之间的线对应在 线数组 中的位置, 然后与正常不需要旋转时的符号进行对比, 若相同则权值为0, 不同则权值为1。
// 左上 右上 左下 右下
ix[] = {-1, -1, 0, 0};
iy[] = {-1, 0, -1, 0};
char cs[] = {'\\', '/', '/', '\\'};在BFS过程中, 若扩展的点已经被搜过, 不能直接丢弃, 有可能之前使用边权为1更新, 这里是用边权为0更新。 过程可以看做一个简化版的dijkstra。
代码
const int N = 510;
typedef pair<int, int> PII;
char g[N][N];
int n, m;
int dist[N][N];
bool st[N][N];
int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, -1, 1};
int ix[] = {-1, -1, 0, 0}, iy[] = {-1, 0, -1, 0};
char cs[] = "\\//\\";
int bfs()
{
deque<PII> q;
memset(dist, 0x3f, sizeof dist);
memset(st, false, sizeof st);
dist[0][0] = 0;
q.push_back({0, 0});
while (q.size())
{
auto t = q.front();
q.pop_front();
int x = t.first, y = t.second;
if (x == n && y == m)
return dist[x][y];
if (st[x][y])
continue;
st[x][y] = true;
for (int i = 0; i < 4; i++)
{
int xa = x + dx[i], yb = y + dy[i];
if (xa < 0 || xa > n || yb < 0 || yb > m)
continue;
int ga = x + ix[i], gb = y + iy[i];
int w = g[ga][gb] != cs[i];
if (dist[xa][yb] > dist[x][y] + w)
{
dist[xa][yb] = dist[x][y] + w;
if (!w)
q.push_front({xa, yb});
else
q.push_back({xa, yb});
}
}
}
return -1;
}
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> g[i];
if ((n + m) % 2)
cout << "NO SOLUTION" << endl;
else
cout << bfs() << endl;
}
return 0;
}