网页
资讯
视频
图片
知道
文库
贴吧
地图
采购
进入贴吧
全吧搜索
吧内搜索
搜贴
搜人
进吧
搜标签
日
一
二
三
四
五
六
签到排名:今日本吧第
个签到,
本吧因你更精彩,明天继续来努力!
本吧签到人数:0
一键签到
可签
7
级以上的吧
50
个
一键签到
本月漏签
0
次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行
补签
。
连续签到:
天 累计签到:
天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
12月28日
漏签
0
天
数毒吧
关注:
336
贴子:
2,203
看贴
图片
吧主推荐
玩乐
10
回复贴,共
1
页
<返回数毒吧
>0< 加载中...
唯一环的路径不唯一性
只看楼主
收藏
回复
Sunnie
带鳍鱼
7
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
之前有人问我这么一个问题:唯一环的路径是唯一的吗?这一下把我问懵了,我研究了一两天,结果发现这个问题其实并不是特别难。经和楠竹讨论,现在把结果发上来。
至于大家是不是真正知道这个问题,我希望比我们先知道结果的人不要充当**人士。知道结果的话,请你绕行。
送TA礼物
IP属地:北京
1楼
2021-01-10 12:43
回复
Sunnie
带鳍鱼
7
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
现在阐述一下问题:唯一环(UL)的路径是否是唯一的。什么是唯一环的路径呢?就是说,我们需要把唯一环的环状结构按照次序有序连接起来,作为唯一环的先后序列。题目问的就是这个序列是否存在多种不同的连法。举个例子,这个UL的路径是这样的:
可以从图里看到,这个连法是唯一的。换句话说,你无法找到一个点,在和别的点连起来之后,依然成环。比如我们可以尝试把r4c6和r4c8连起来,但是这样的话,剩余的格子无法保证路径成环。
IP属地:北京
2楼
2021-01-10 12:46
回复
收起回复
Sunnie
带鳍鱼
7
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
下面说一下基本概念:出度。我们把一个点可以往外连的所有格子总数称为这个格子的出度。比如r4c6的出度是3,因为它可以往结构的r1c6、r6c4和r4c8三个格子连接线条。
当出度点均为2的时候,UL的路径唯一,因为我们无法找到别的连接办法,因为它只有两种连接方式。
IP属地:北京
3楼
2021-01-10 12:48
回复
收起回复
Sunnie
带鳍鱼
7
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
当出度为3的时候,当这个点作为接收的时候,剩下出度为2,即还可以往外找到两种可能连接的情况。这种情况分析较为复杂。下面我找到了一个极端例子:所有出度都是3的UL,且它至少有4种不同的路径。
如图所示,所有点的出度都是3,也就是说我们无法找到出度为2的点。
IP属地:北京
4楼
2021-01-10 12:51
回复
收起回复
Sunnie
带鳍鱼
7
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
最后一个路径是SE程序给出的默认路径。可以从图里看到,路径是不对称的,所以你可以尝试把路径旋转180度后得到第四种画法。
IP属地:北京
5楼
2021-01-10 12:52
回复
收起回复
Sunnie
带鳍鱼
7
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
结论:但是出度3的点会受到出度2的点的制约,所以我们连线先从出度2的连的话,出度3的点就会由于刚才的连锁反应而降到出度2,因为别的点可能被别的地方连走了,所以平时我们遇不到多路径的UL。
图里给出的恰好是范例,所有点都是出度3,这样你怎么找到一种,就必然有一种对称的画法。
出度3的点在UL较长的时候出现频率较高,但这样的点依旧可以受到别的出度2的点的制约而改成出度2,进而只有一种连接方式,导致一种巧合。
如图所示,所有圈起来的点都是出度3的点。
就这个例子来说,比如我们假设把r1c5的格子挪一下,假如我往下放一个格子的位置,然后为了保证UL合法,我们把r2c7的点往上挪一下。
图里的这样的结构就有两种画法,所以路径不一定是唯一的。
IP属地:北京
6楼
2021-01-10 12:56
回复
收起回复
Sunnie
带鳍鱼
7
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
在UL的递归算法过程中,我们是通过BFS对行、列、宫三个方向进行迭代。由于迭代方式的关系,所以算法不能给出唯一的路径;但我们找到的例子里,大多的题目都是唯一的路径,这使得我们以为路径唯一是一个“定则”。所以在我们平时做题和发现问题的时候,需要反复思考,不能认为巧合是真理就不再思考了。
IP属地:北京
7楼
2021-01-10 12:58
回复
收起回复
中佑moatlzy
唯余
2
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
UL有子环的可能性吗?
8楼
2021-01-13 08:56
回复(2)
收起回复
贴吧用户_aD2eKP4
排除法
1
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
路径唯一才叫唯一环。路径有分支,但最终构成封闭的环,也算唯一环。
只要逻辑上符合强弱交替并形成封闭的环,那结论是一致的。
9楼
2021-04-20 17:21
回复
收起回复
登录百度账号
扫二维码下载贴吧客户端
下载贴吧APP
看高清直播、视频!
贴吧热议榜
1
2024贴吧年度盘点
2648730
2
美媒称中国新型战机令人震惊
2019966
3
C罗炮轰金球奖不公平
2007768
4
YSKM爆料S15新赛制
1412262
5
曝徐娇被起诉
1397318
6
崩铁3.1新角色缇宝公布
1288125
7
韩媒曝Zeus军训被霸凌
1108656
8
徐娇为《雄狮少年》怼素人
1017060
9
米哈游跌出手游收入前三
742522
10
《清明上河图密码》豆瓣7分
646590
贴吧页面意见反馈
违规贴吧举报反馈通道
贴吧违规信息处理公示