网页
资讯
视频
图片
知道
文库
贴吧
地图
采购
进入贴吧
全吧搜索
吧内搜索
搜贴
搜人
进吧
搜标签
日
一
二
三
四
五
六
签到排名:今日本吧第
个签到,
本吧因你更精彩,明天继续来努力!
本吧签到人数:0
一键签到
可签
7
级以上的吧
50
个
一键签到
本月漏签
0
次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行
补签
。
连续签到:
天 累计签到:
天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
01月16日
漏签
0
天
数毒吧
关注:
339
贴子:
2,203
看贴
图片
吧主推荐
玩乐
6
回复贴,共
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
回复
收起回复
登录百度账号
扫二维码下载贴吧客户端
下载贴吧APP
看高清直播、视频!
贴吧热议榜
1
崩铁3.0剧情节奏再起
1546890
2
LOL就蓝色精粹问题道歉
1251321
3
细数吉田修平在索尼的功过
1119888
4
马斯克母亲小红书评论两极分化
870534
5
尹锡悦不穿囚服在牢里看电视
838006
6
英伟达CEO黄仁勋现身深圳
740775
7
谁给洋人指路素食吧的
520128
8
洛杉矶富人雇私人消防躲过山火
364734
9
以色列与哈马斯达成停火协议
309298
10
盘点那些长得很像的角色
234297
贴吧页面意见反馈
违规贴吧举报反馈通道
贴吧违规信息处理公示