当前位置: 首页 > news >正文

信息学奥赛一本通 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 ∗ m n*m nm个正方形,因此一共有 ( n + 1 ) ∗ ( m + 1 ) (n+1)*(m+1) (n+1)(m+1)个顶点,各顶点所在行号范围为0~n,列号范围为0~m。
一个顶点(sx,sy)可能直接到达的顶点为其左上、右上、右下、左下四个顶点,用0,1,2,3表示这4个方向,每个方向的下一个顶点如下:

编号方向该方向下一个顶点
0左上(sx-1, sy-1)
1右上(sx-1, sy+1)
2右下(sx+1, sy+1)
3左下(sx+1, 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)的右下方向和(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";elsecout << ans;return 0;
}
http://www.lryc.cn/news/494063.html

相关文章:

  • k8s删除网络组件错误
  • MySQL之JDBC
  • 音视频入门基础:MPEG2-TS专题(10)——PAT简介
  • ElementUI:el-drawer实现在父组件区域内打开抽屉组件非全屏
  • Vue教程|搭建vue项目|Vue-CLI2.x 模板脚手架
  • jmeter学习(7)命令行控制
  • BGP协议路由黑洞
  • 存储结构及关系(一)
  • 玄机应急:linux入侵排查webshell查杀日志分析
  • python爬虫安装教程
  • 田忌赛马五局三胜问题matlab代码
  • Spring循环依赖问题的解决
  • KAN-Transfomer——基于新型神经网络KAN的时间序列预测
  • 鸿蒙学习自由流转与分布式运行环境-价值与架构定义(1)
  • 【k8s深入理解之 Scheme 补充-2】理解 register.go 暴露的 AddToScheme 函数
  • uni-app写的微信小程序每次换账号登录时出现缓存上一个账号数据的问题
  • 数据分析流程中的Lambda架构,以及数据湖基于Hadoop、Spark的实现
  • Android 原生解析 Json 字符串
  • Windsurf可以上传图片开发UI了
  • Qt UI设计 菜单栏无法输入名字
  • blender 视频背景
  • 【python】OpenCV—Tracking(10.5)—dlib
  • 音视频入门基础:MPEG2-TS专题(9)——FFmpeg源码中,解码TS Header的实现
  • 解决“磁盘已插上,但Windows系统无法识别“问题
  • 论文笔记-WWW2024-ClickPrompt
  • 53 基于单片机的8路抢答器加记分
  • 【java数据结构】二叉树OJ题
  • IIC和SPI的时序图
  • MySQL数据库表的操作
  • .net core 创建linux服务,并实现服务的自我更新