网站开通支付宝收款,网站建设公司-跨界鱼科技,国外景观设计网站,民航资源网【题目链接】
ybt 1448#xff1a;【例题1】电路维修 洛谷 P4667 [BalticOI 2011 Day1] Switch the Lamp On 电路维修
【题目考点】
1. 双端队列广搜#xff08;0-1BFS#xff09;
【解题思路】
整个电路是由一个个的正方形的电路元件组成#xff0c;每个正方形有四个…【题目链接】
ybt 1448【例题1】电路维修 洛谷 P4667 [BalticOI 2011 Day1] Switch the Lamp On 电路维修
【题目考点】
1. 双端队列广搜0-1BFS
【解题思路】
整个电路是由一个个的正方形的电路元件组成每个正方形有四个角也就是四个点。每个点作为拓扑图中的一个顶点。一共有 n ∗ m n*m n∗m个正方形因此一共有 ( n 1 ) ∗ ( m 1 ) (n1)*(m1) (n1)∗(m1)个顶点各顶点所在行号范围为0~n列号范围为0~m。 一个顶点(sx,sy)可能直接到达的顶点为其左上、右上、右下、左下四个顶点用0123表示这4个方向每个方向的下一个顶点如下
编号方向该方向下一个顶点0左上(sx-1, sy-1)1右上(sx-1, sy1)2右下(sx1, sy1)3左下(sx1, sy-1)
将各方向顶点坐标与(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)的右下方向和(i1, j1)的左上方向有导线如果为/那么(i1, j)的右上方向和(i, j1)的左下方向有导线
设从顶点(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)的最短路径长度可以使用双端队列广搜完成。
双端队列广搜的基本步骤为
设双端队列保存状态该问题的状态包括到达顶点位置(x, y)以及从(0,0)出发到(x,y)的路径长度dis。将起始状态【顶点(0,0)路径长度0】入队每次循环出队一个状态【顶点(sx, sy)路径长度dis】从该状态中的顶点扩展到其邻接点一步可以走到的相邻的位置【顶点(x, y)】通过con数组取到从(sx, sy)到(x, y)的边的权值。 如果边权为1那么新的状态【顶点(x,y)路径长度dis1】队尾入队如果边权为0那么新的状态【顶点(x,y)路径长度dis】队头入队 可以增加优化设vis数组记录已经出队的顶点如果某一顶点已经出队则如果该顶点再次出队则不再扩展访问其邻接点。 因为这一次扩展得到的路径长度dis一定大于等于前一次扩展得到的路径长度dis对于求最短路问题而言这一次扩展到的结果一定不是最优解没有必要仅扩展。 如果出队的顶点是终点返回到达终点的最短路径长度。如果队列不断出队直至为空也没有访问到终点则返回-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()
{dequePath 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 sxdir[i][0], y sydir[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, dis1});}}}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[i1][j][1] con[i][j1][3] true;else//c \\con[i][j][2] con[i1][j1][0] true;}int ans bfs();if(ans -1)cout NO SOLUTION;elsecout ans;return 0;
}
