地图上能从甲房间到乙房间,不代表还能回到甲。把能够互相到达的房间归为同组,可以看清哪些区域内部可往返、哪些连接只有单向作用。
六个房间使用有向边连接,允许多步行走,也把原地停留视为可达。两房间只有在两个方向都可达时才归入同一组,再把跨组边压缩成区域之间的连接。
单向边[起点,终点][(0, 1), (0, 5), (1, 0), (1, 2), (2, 3), (3, 5), (4, 3), (5, 0), (5, 1)]
房间0可到达[0, 1, 2, 3, 5],属于区域0,区域内房间[0, 1, 2, 3, 5]都能与它互相返回。
房间1可到达[0, 1, 2, 3, 5],属于区域0,区域内房间[0, 1, 2, 3, 5]都能与它互相返回。
房间2可到达[0, 1, 2, 3, 5],属于区域0,区域内房间[0, 1, 2, 3, 5]都能与它互相返回。
房间3可到达[0, 1, 2, 3, 5],属于区域0,区域内房间[0, 1, 2, 3, 5]都能与它互相返回。
房间4可到达[0, 1, 2, 3, 4, 5],属于区域1,区域内房间[4]都能与它互相返回。
房间5可到达[0, 1, 2, 3, 5],属于区域0,区域内房间[0, 1, 2, 3, 5]都能与它互相返回。
共2个区域[[0, 1, 2, 3, 5], [4]],压缩后的单向连接[(1, 0)]。跨组可达不自动意味着跨组可返回;若两个组间存在双向可达路径,它们应当已经归成同一个组。
先列出每个房间可到达的集合,再找相互可达的等价组。压缩后的不同区域之间不应还有有向循环,否则循环中的区域其实可以互相到达,应当合并。
建议先按原始数据自己算一遍,保留中间状态后再与本例对照。发生分歧时,先寻找最早不同的步骤,检查边界是否包含、编号与坐标方向是否一致,以及状态是在事件之前还是之后更新。最终结果相同并不能替代对过程规则的理解,修改输入后也需要重新核算。
这只是通行关系,未计算距离、消耗或开门条件。地图若有钥匙、临时门或状态切换,应把条件加入状态,不能直接把一张固定通道图当成所有情况下都可返回的保证。
以便获取最新的优惠活动以及最新资讯!