塔防游戏 道路编辑器Q13 E02

背景

现在需要支持地图的建造和编辑。

地图在一开始是一片草原，没有任何马路。

我们需要支持在草原上设置起始点、终点、以及修建道路

在修建的过程中，地图可能进入非法状态，比如道路没有联通。

ADT

功能

功能是基于 上一个版本上新增的功能

start: Point

能够 设置 路在地图上结束的点

end: Point

能够 设置 路在地图上开始的点

addRoad(from: Point, to: Point)

在 from 到 to 之间修建一条路

假设 from 和 to 一定是在同一行 或者同一列

isValid(): Bool

路是否是合法的

一个开始点，一个结束点。并且开始点到结束点之间路都连着，并且没有分叉

destroy(from: Point, to: Point)

删除 from 到 to 之间 任何一个马路格子

假设 from 和 to 一定是在同一行 或者同一列

要求

代码实现

尝试写出实现代码

代码分析

针对现有的解决方案，研究每个功能的时间复杂度是多少。

你需要自己定义 $O(n)$ 中的 $n$ 是什么，是路的长度，还是方块的个数 等等。

结构设计

思考，是否更换其他的内存结构，能够在某些地方上降低代码量，或者降低时间复杂度