信息学奥赛一本通 1448：【例题1】电路维修 | 洛谷 P4667 [BalticOI 2011 Day1] Switch the Lamp On 电路维修

【题目链接】

ybt 1448：【例题1】电路维修
洛谷 P4667 [BalticOI 2011 Day1] Switch the Lamp On 电路维修

【题目考点】

1. 双端队列广搜（0-1BFS）

【解题思路】

整个电路是由一个个的正方形的电路元件组成，每个正方形有四个角，也就是四个点。每个点作为拓扑图中的一个顶点。一共有$n\ast m$个正方形，因此一共有$(n+1)\ast (m+1)$个顶点，各顶点所在行号范围为0~n，列号范围为0~m。
一个顶点(sx,sy)可能直接到达的顶点为其左上、右上、右下、左下四个顶点，用0，1，2，3表示这4个方向，每个方向的下一个顶点如下：

将各方向顶点坐标与(sx,sy)的差值保存在dir数组int dir[4][2] = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};，方便通过某一顶点扩展出其可以到达的顶点。
第i行第j列顶点(i,j)是第i行第j列正方形的左上角顶点。

设con数组，con[i][j][d]表示一个(i,j)顶点在d表示的方向上是否有导线。
通过输入得到第i行第j列正方形的导线方向

• 如果为\，那么(i,j)的右下方向和(i+1, j+1)的左上方向有导线
• 如果为/，那么(i+1, j)的右上方向和(i, j+1)的左下方向有导线

设从顶点(sx,sy)在d方向扩展到的下一个顶点为(x,y)，那么con[sx][sy][d]就表示(sx, sy)到(x,y)是否有导线

• 如果从(sx, sy)到(x,y)有导线，那么说明在拓扑图中，从顶点(sx, sy)到顶点(x,y)不需要任何花费，两顶点之间有一条权值为0的边。
• 如果从(sx, sy)到(x,y)没有导线，那么需要将该正方形元件转动一次后，才能让两个顶点之间有导线相连。说明在拓扑图中，从顶点(sx, sy)到顶点(x,y)需要1单位的花费，两顶点之间有一条权值为1的边。
• 因此，该图是边权只有0、1的图。

该题求的是从左上角(0,0)到右下角(n,m)有导线通路的最小转动正方形的次数，即为拓扑图中从顶点(0,0)到顶点(n,m)的最短路径长度，可以使用双端队列广搜完成。

双端队列广搜的基本步骤为：

1. 设双端队列保存状态，该问题的状态包括到达顶点位置(x, y)，以及从(0,0)出发到(x,y)的路径长度dis。
2. 将起始状态：【顶点(0,0)，路径长度0】入队
3. 每次循环出队一个状态【顶点(sx, sy)，路径长度dis】，从该状态中的顶点扩展到其邻接点（一步可以走到的相邻的位置）【顶点(x, y)】，通过con数组取到从(sx, sy)到(x, y)的边的权值。
   • 如果边权为1，那么新的状态【顶点(x,y)，路径长度dis+1】队尾入队
   • 如果边权为0，那么新的状态【顶点(x,y)，路径长度dis】队头入队
4. 可以增加优化：设vis数组记录已经出队的顶点，如果某一顶点已经出队，则如果该顶点再次出队，则不再扩展访问其邻接点。

   因为这一次扩展得到的路径长度dis一定大于等于前一次扩展得到的路径长度dis，对于求最短路问题而言，这一次扩展到的结果一定不是最优解，没有必要仅扩展。

5. 如果出队的顶点是终点，返回到达终点的最短路径长度。如果队列不断出队直至为空，也没有访问到终点，则返回-1，表示不存在从起点到终点的最短路径。

【注意】不能使用dis二维数组记录到达某个顶点的最短路径长度，因为双端队列广搜过程中，一个顶点可能会被多次扩展得到。每次扩展到该顶点时，步数可能更大也可能更小，不方便处理。

最后如果得到从起点到终点的最短路径，输出。如果得不到，输出NO SOLUTION

【题解代码】

解法1：双端队列广搜

#include <bits/stdc++.h>
using namespace std;
#define N 505
struct Path
{
	int x, y, dis;//存在一条到达(x, y)的长为dis的路径	
};
int n, m;
int dir[4][2] = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};//0:左上 1：右上 2：右下 3：左下 
bool con[N][N][4];//con[i][j][d]：(i,j)向d方向是否有导线
bool vis[N][N];//到达(x,y)的路径是否已出队 
int bfs()
{
	deque<Path> dq;
	dq.push_front(Path{0, 0, 0});
	while(!dq.empty())
	{
		int sx = dq.front().x, sy = dq.front().y, dis = dq.front().dis;
		dq.pop_front();
		if(vis[sx][sy])
			continue;
		vis[sx][sy] = true;
		if(sx == n && sy == m)
			return dis;
		for(int i = 0; i < 4; ++i)
		{
			int x = sx+dir[i][0], y = sy+dir[i][1];
			if(x >= 0 && x <= n && y >= 0 && y <= m)
			{
				if(con[sx][sy][i])//权值0 
					dq.push_front(Path{x, y, dis});
				else//权值1 
					dq.push_back(Path{x, y, dis+1});
			}
		}
	}
	return -1;
}
int main()
{
	char c;
	cin >> n >> m;
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j)
		{
			cin >> c;
			if(c == '/')
				con[i+1][j][1] = con[i][j+1][3] = true;
			else//c == '\\'
				con[i][j][2] = con[i+1][j+1][0] = true;
		}
	int ans = bfs();
	if(ans == -1)
		cout << "NO SOLUTION";
	else
		cout << ans;
	return 0;
}