塔防游戏 地图数据结构Q13 E01

背景

在一个二维地图上，有一条马路占据着一些格子。

马路没有铺设的格子 就是草坪。

我们需要一个数据结构表达它，并且完成一些功能

假设已知数据结构

Point 
+   x: Int 
+   y: Int 

ADT

特性

游戏的地图是 标准的二维方格地图

在地图上一定会有一条路

路一定是横平竖直的

路可能会拐弯

路一定没有分叉

路一定只有 1个起始点，和 1个结束点

路至少占2个格

功能

start: Point

能够 获取 路在地图上结束的点

意思就是 只有 getter，没有 setter

end: Point

能够 获取 路在地图上开始的点

意思就是 只有 getter，没有 setter

onRoad(location: Point) : Bool

返回 location 这个坐标的位置上是否是马路，还是草坪

length(): Int

返回路的长度，总共多少个格子

distanceToEnd(from: Point): Int

返回从 from 点到 终点 有多少个格子

要求

结构设计

根据上述 ADT 写出 GameMap 数据结构内部的设计。

使用什么样的数据结构可以可以完成上面这些功能

可以使用基本组成元素 以及 已经学过的 数据结构

代码实现

尝试写出实现代码

写代码时，你可能需要一个函数来初始化你的内存结构

代码分析

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

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