SGU 101 Domino 题解
2024-08-29 16:05:40
鉴于SGU题目难度较大,AC后便给出算法并发布博文,代码则写得较满意后再补上。——icedream61
题目简述:暂略
AC人数:3609(2015年7月20日)
算法:
这题就是一笔画,最多只有7个点(0~6),每个骨牌就是一条双向边。
要做的,就是找出一条一笔画的路径。步骤如下:
1. 读入数据,建成图。
2. 判断可否一笔画。一笔画条件:奇点数为0或2 + 联通分量数为1。
3. 如果不可一笔画,则输出No solution,结束;如果可以,则找到一条路径R,并输出。
下面给出找一笔画路径R的经典算法:
1. 找到起点S和终点T
如果有两个奇点,那么一个为S一个为T;
如果没有奇点,那么随便选一个点,S和T都是它。
2. 随便找一条S→T的路径,这就是初始的R。过程中,走过一次的边便标记为失效,今后视而不见(注意,这题可是双向边!)。
3. 若此时图中依旧有剩余边,则在R的基础上,不断更新,直至图中没有剩余边。更新方法如下:
(a)从R中任一点出发,走图中剩余的边,直至回到此点,这就找到了一条路径r。
(b)把R中此点的位置,换成路径r,这就更新了R。
4. 此时图中已没有剩余边,R即为所求一笔画路径。
可以证明,只要有一笔画路径,这个算法必然可以找到。
最新文章
- 理解TCP三次握手/四次断开的必要性
- 大话设计模式C++版——装饰模式
- 在SharePoint2010中用out-of-box的方式自定制Application Pages(AccessDenied,Confirmation,Error,Login,RequestAccess,Signout,WebDeleted)
- QuartZ.net 常用配置说明
- iOS AVKit音视频播放全面详解
- C4D to Unity3D插件C2U Tool开源发布!简化你的工作流
- 安装VC6提示找不到ACME时的解决办法
- yii2 文件上传
- nexcel 读取 excel
- 表情键盘及文字表情识别简单demo
- selenium 调用JS操作滚动条(java)来解决element not clickable的问题
- ExtJS4加载FormPanel数据的几种方式
- windows下Memcached 架设及java应用
- 使用wcf编写坐标字符串生成shapefile文件,在iis发布供前端调用
- UVA - 11082 Matrix Decompressing(最大流+行列模型)
- spring-oauth-server实践:使用授权方式四:client_credentials 模式下access_token做业务!!!
- eval和列表解析的一处陷阱
- Leetcode 88. Merge Sorted Array(easy)
- 解决radio、select表单返回时,再次选择失效
- UML中的六种关系