好的，我将按照刚才的模板为这道题写一个清晰的题解。

---

「POI2017 R2」城堡 Castle 题解

题目理解

我们有一个 $w \times h$ 的网格地图，被 $n$ 个矩形房间完全覆盖且互不重叠。两个房间如果有公共边（长度 ≥ 1）则连通。部分房间内有危险点，不能进入。求从起点到终点的最少经过房间数。

关键约束：

• 房间是矩形，边在网格线上
• 房间完全覆盖地图且不重叠
• 危险点位于房间内部
• 起点和终点所在房间保证安全

问题转化

设：

• $G = (V, E)$ 是一个无向图，节点是房间
• 边 $(u,v)$ 存在当且仅当房间 $u$ 和 $v$ 有公共边
• $D \subseteq V$ 是包含危险点的房间集合
• $s$ = 起点所在房间，$t$ = 终点所在房间

问题转化为：在 $G$ 中找从 $s$ 到 $t$ 的最短路径，且不经过 $D$ 中的节点。

核心难点

1. 建图：$w,h$ 可达 $10^9$，不能直接处理网格
2. 房间定位：给定坐标 $(x,y)$，要快速找到所在房间
3. 邻接关系：高效找出有公共边的房间对

算法框架

1. 房间定位（Point Location）

对于每个点 $(x,y)$，找到包含它的房间：

扫描线 + 区间树：

• 将所有房间的左右边界作为事件 (x, \text{type}, \text{room_id}, y_1, y_2)
• 从左到右扫描，用平衡树维护当前 $y$ 区间对应的房间
• 对于查询点 $(x,y)$，在扫描到 $x$ 时查询 $y$ 所在的房间

时间复杂度：$O((n+m)\log n)$

2. 邻接关系建立

两个房间相邻 ⇔ 有公共水平边或垂直边

垂直相邻（水平扫描线）：

• 事件：(x, \text{left/right}, \text{room_id}, y_1, y_2)
• 扫描过程中，新加入的矩形与当前活跃矩形在 $y$ 区间上有重叠 ⇒ 相邻

水平相邻（垂直扫描线）：

• 事件：(y, \text{bottom/top}, \text{room_id}, x_1, x_2)
• 类似处理

时间复杂度：$O(n\log n)$

3. 图搜索

在建立的图上进行 BFS：

dist = [-1] * n
queue = deque()
if s not in D:
    dist[s] = 1
    queue.append(s)
while queue:
    u = queue.popleft()
    for v in adj[u]:
        if v not in D and dist[v] == -1:
            dist[v] = dist[u] + 1
            queue.append(v)
return dist[t]

关键实现细节

数据结构选择：

• 使用 map 维护区间集合：map<y_range, room_id>
• 扫描线事件排序处理

边界处理：

• 矩形是闭区间 $[x_1,x_2] \times [y_1,y_2]$
• 相邻判定要确保公共边长度 ≥ 1

危险房间标记：

• 对每个危险点定位房间后标记
• 保证起点终点房间安全

复杂度分析

• 预处理：$O(n\log n)$ 建图 + $O(m\log n)$ 危险标记
• 查询：$O(n)$ BFS
• 总复杂度：$O((n+m)\log n)$

算法标签

• 计算几何
• 扫描线算法
• 区间树 / 平衡树
• 图论 BFS
• 平面图处理

样例分析

样例中：

• 危险房间：2号（含(4,2),(5,2)）、7号（含(4,4)）
• 起点在房间1，终点在房间9
• 最短路径：1 → 6 → 8 → 9（4个房间）

总结

本题是典型的几何建图 + 图搜索问题，核心在于利用扫描线高效处理大规模网格上的矩形关系。通过将几何条件转化为图论问题，再利用经典算法求解，体现了计算几何与图论的结合应用。

对于 $n,m \leq 10^6$ 的数据规模，$O(n\log n)$ 的算法是可行的，关键在于扫描线数据结构的正确实现。