能否把地图的每条通道恰好走过一次:独立观察第07例
有些连线关卡要求每条通道只走一次,而不是每个房间只进入一次。这两种目标不同,同一个房间在合法路线中可能被多次经过。
本例为无向图,没有重复通道或自环。先忽略没有通道的孤立房间,检查其余房间是否连通,再数奇数度房间:零个时可形成闭合路线,两个时可以从一个奇数度房间走到另一个,其他数量不能完成。
输入与计算记录
房间编号零至六,完整通道为[(0, 3), (0, 5), (0, 6), (1, 2), (1, 6), (2, 5), (3, 4)]。
房间 | 连接数 | 奇偶 0 | 3 | 奇 1 | 2 | 偶 2 | 2 | 偶 3 | 2 | 偶 4 | 1 | 奇 5 | 2 | 偶 6 | 2 | 偶 有通道房间连通:True 奇数度房间:[0, 4] 是否可完成:True 一条合法房间序列:[0, 5, 2, 1, 6, 0, 3, 4]
阅读记录时先确认编号代表的是格子、对象、时间还是数组位置,再逐项对应输入与输出。中间状态提供了定位差异的依据,最后的一个合计数字不能替代全部步骤;没有对象的集合与数值零也应区别看待。
怎样检查这个结果
给出的路线必须逐步对应真实通道,恰好使用所有通道各一次。路线长度按边数计算,房间序列长度应比通道数多一;孤立房间没有待走通道,不要求另外访问。
结论针对当前无向通道图,不包含单向门、移动消耗或必须从指定房间出发的附加条件。加入这些限制后需要另外检查,不能只看到奇数度数量合适就忽略连通性与起点约定。
可以遮住结果表先按规则复算第一步,再选择一个边界输入重复操作。若更换规则中的任一前提,应重新推导结果,不要只调整最后答案。这样既能理解本例为何成立,也能看清它在哪些情况下不再适用。
