在做算法竞赛题目的时候我最大的感受是很多所谓“难”的题其实不是代码量大也不是某个算法特别复杂而是题目本身披了一层“故事外衣”你得把那层外衣剥掉之后才能看到里面真正要求的东西。UVa 11509 Touring Robot 就是典型的这一类题目。这题在 UVa 的题库里不算特别热门但做过的都知道它其实非常能考察一个人对“几何问题算法化”的理解程度。如果你刚刷完计算几何的基础题想挑战一下把几何建模和图搜索结合在一起的题目那么这题会是很好的练手对象。我第一次做这题的时候其实是被“机器人”“Touring”这些词给带偏了以为是要处理什么路径规划或者运动学的问题。实际上题目给的是一个多边形这个多边形代表障碍物或者围墙的边界然后给了一个圆形的机器人让这个机器人从起点走到终点问你它能不能到达以及如果不考虑起点和终点本身的位置单纯判断路径是否与障碍区域冲突。这里最关键的一步就是把“圆形的机器人”转化为“一个点”然后把障碍物边界向外扩张一个半径。这个转化一旦想明白后面的搜索和图建模就顺理成章了。这篇文章我会从题目类型判断、几何转化、搜索策略、代码实现到坑点排查一步步带你走一遍完整的做题流程。1. 题目解读与解题思路拆解1.1 读懂题目的“话外音”很多 UVa 的题目在表述上都非常克制它不会直接告诉你“这是一个多边形障碍物避障问题”而是要用场景去包装。Touring Robot 这道题核心场景是有一个机器人通常抽象成圆形在一个有边界限制的区域内移动区域内可能存在障碍物要求判断从起点到终点是否可行或者求最短路径。这类题有几个典型的特征词robot、circle、polygon、tour、collision、blocked。如果你在题面里看到这些词第一直觉应该是往“几何 搜索”的方向去靠而不是直接去想机器人运动学。因为题目对机器人的控制方式通常描述得极其简单要么是“任意方向移动”要么是“按顺序访问若干个点”而绝对不会涉及加速度、摩擦力这些东西。所以它本质上就是一个纯几何可达性问题。拿这道题来说机器人被抽象成一个圆这个圆在移动过程中不能与多边形边界相交也不能越过边界。那么问题就变成给定一个圆它的圆心从起点移动到终点运动过程中圆始终不能和多边形相交。这里“相交”的判定是解题的核心。1.2 为什么核心思路是“圆缩点、多边形扩张”相交判定如果直接做要计算圆与每条边的距离还要判断圆心在多边形内部还是外部圆心距离边界多少个半径以及圆心路径是否安全。这样不是不能做但很啰嗦而且在路径搜索时会非常麻烦因为搜索的是“圆心位置”但约束条件是“整个圆都不越界”。这时候就要用到一个很经典的几何变换——Minkowski Sum闵可夫斯基和。这个概念听起来很高深但通俗地说就是当一个半径为 r 的圆的圆心在运动时圆心能到达的所有位置的集合等于原来的可通行区域往外“膨胀”一圈得到的区域。反过来如果我们把圆心当成一个点那么原来的障碍物边界也要往外膨胀一圈膨胀的半径刚好等于 r。举个例子假设走廊宽度原本是 3机器人半径是 2那么圆心可通行的走廊宽度实际上是 3 - 2×2 -1也就是根本过不去。用“圆缩点、多边形扩张”的视角来看就是把走廊的两面墙各自向外平移 2 个单位平移之后两面墙重叠了说明圆心没有安全路径。这样处理就把“圆和线段相交”的判定问题转化成了“点和线段距离”的判定问题。在实际代码里我们不需要真的把这个膨胀后的多边形完整构造出来——因为复杂多边形的外扩往往会引入圆弧边处理起来非常麻烦。我们只需要在做碰撞检测时把“点是否在多边形内”这个判断改成“点到多边形任意一条边的距离是否小于 r或者点是否在多边形内部”。等价于说圆心点所在的位置如果离任意一条边的距离小于 r或者本身已经落进多边形里那就视为不合法状态。这样做既绕开了构造圆弧边的麻烦计算结果也和真正的 Minkowski 和完全一致。1.3 这题的解题链路与算法选型明确了“圆缩点”的思路之后整条解题链路就很简单了读取多边形顶点读取机器人半径读取起点和终点。如果起点或终点本身就不合法离多边形某条边太近或者落在多边形内部直接输出不可达。把可通行区域离散化成网格或者直接用连续的几何信息做路径搜索。从起点开始搜索如果能够不碰到膨胀后的障碍物边界到达终点就认为可达。这里的关键问题是用什么方式去搜。选择不同代码复杂度差别非常大。如果题目的数据范围很小比如地图只有几十个单位宽我们可以用 BFS 在离散网格上搜索。如果坐标范围很大但顶点数很少那么我们可以直接用几何图的方式进行搜索把起点、终点和多边形的顶点作为图上的节点任意两个节点之间如果存在一条不与障碍物相交的直线路径就在它们之间连边然后跑最短路径算法。如果多边形数量多、顶点数也多可能就要用更复杂的 visibility graph 或者 A* 变种。对于 UVa 11509 这道题我印象中数据范围并不算大用“离散网格 BFS 每步碰撞检测”是完全可行的也是最好理解、最容易写对的一种方案。如果你是在比赛现场做这题我建议优先选择 BFS 网格法因为它的思维量最小边界情况最好控制写完了也容易调试。后面我会重点讲这种方案的具体实现。2. 几何体预处理与碰撞检测细节2.1 在代码中表示多边形和圆UVa 类题目的几何题最常用的数据结构就是两个 double 变量表示一个点然后用 vector 存点的序列。多边形通常是按顺序给出的可能是顺时针也可能是逆时针这个顺序在某些算法里很重要但在判断“点是否在多边形内部”时射线法对顶点顺序不敏感所以我们不用太担心方向问题。struct Point { double x, y; Point(double x 0, double y 0) : x(x), y(y) {} }; using Polygon vectorPoint;机器人半径 r 是一个正数起点和终点各自是一个 Point。这里要注意题目里给的半径可能不是整数所以所有涉及几何计算的变量都应该用 double避免整数除法带来的精度问题。UVa 的题目对精度要求通常卡得不是特别死一般 eps 取 1e-9 就够用。2.2 点到线段距离的计算在碰撞检测里最核心的几何计算就是“圆心到多边形每条边的距离”。这里的“边”是线段不是一个无限长的直线。很多新手在这里会犯错直接套用点到直线的距离公式结果把线段延长线上的点也算进去了导致本不应该碰撞的情况被判成碰撞。点到线段的距离需要分两种情况如果投影点在线段上那么距离就是垂线段的长度。如果投影点在线段端点之外那么距离就是该点到最近端点的距离。代码实现上最常见的方式是通过点积去判断double distToSegment(Point p, Point a, Point b) { double dx b.x - a.x; double dy b.y - a.y; double len2 dx * dx dy * dy; double t ((p.x - a.x) * dx (p.y - a.y) * dy) / len2; t max(0.0, min(1.0, t)); double projX a.x t * dx; double projY a.y t * dy; double ex p.x - projX; double ey p.y - projY; return sqrt(ex * ex ey * ey); }这里 t 本质上就是投影点在线段上的归一化位置。t0 表示投影在 a 点t1 表示投影在 b 点。通过 clamp 到 [0,1] 区间就自动处理了端点的情况。很多算法模板里会把 eps 直接加进距离判断里我个人习惯是只用一个全局的 EPS在最终比较时做容差。2.3 点与多边形的包含关系判断除了离边的距离我们还需要判断一个点是否在多边形内部因为如果你从某个缺口进入了多边形区域内部即便你离每条边的距离都大于 r这个状态也仍然是非法的。点是否在多边形内部的经典算法是射线法也叫奇偶规则。从该点向任意方向发出一条射线统计它与多边形边的交点数量。如果交点数是奇数说明点在多边形内如果是偶数说明在多边形外。bool pointInPolygon(Point p, const Polygon poly) { bool inside false; int n poly.size(); for (int i 0, j n - 1; i n; j i) { if ((poly[i].y p.y) ! (poly[j].y p.y) p.x (poly[j].x - poly[i].x) * (p.y - poly[i].y) / (poly[j].y - poly[i].y) poly[i].x) { inside !inside; } } return inside; }这段代码是射线法的经典实现它的原理是水平向右发一条射线检查每条边是否跨越这条射线并判断交点是否在点的右侧。每次跨越就翻转一次 inside 状态。这个实现对于绝大多数情况都是正确的包括多边形是凹多边形的情况。不过这里有个非常容易踩的坑如果点恰好落在多边形的边界上射线法可能会得到不一致的结果。所以在做这个判断之前应该先判断点是否“非常接近”多边形的某条边。如果距离小于某个阈值比如 EPS就直接视为在边界上返回非法状态。代码上的顺序应该是先遍历所有边计算点到线段距离如果小于 r - EPS则非法。再用射线法判断点是否在多边形内部如果是则非法。两者都不触发才认为该点合法。2.4 相交与相切的精度处理最后要特别注意精度问题。几何题最怕的不是算法复杂而是输出结果和标准答案差一点点或者边界情况在 eps 附近摇摆不定。在处理圆形机器人能不能贴着墙走的时候数学上“相切”是合法的因为圆的边缘刚好碰到墙但不穿过去。但浮点数计算里很难精确出现“刚好等于 r”的情况要么是 r - 1e-15要么是 r 1e-15。为了避免这种摇摆一般会在比较时加一个 EPSconst double EPS 1e-9; bool collision(Point p, const Polygon poly, double r) { if (pointInPolygon(p, poly)) return true; for (int i 0; i poly.size(); i) { int j (i 1) % poly.size(); double d distToSegment(p, poly[i], poly[j]); if (d r - EPS) return true; } return false; }这里的 EPS 加上去实际上是在告诉评测系统我们允许圆心离墙的距离稍微比 r 小那么一丁点也视为安全。这个容差足够抵消double 的累积误差又不会大到把真正穿墙的情况放过去。3. BFS 网格搜索与代码实现3.1 把连续坐标转成离散网格既然决定用 BFS 网格法第一步就要确定网格的划分方式。把整个地图按照一定的步长划分成格子每个格子中心点作为一个候选状态。机器人的圆心只能落在这些格子中心点上从一个格子移动到相邻的格子。步长的选择非常关键。选得太大路径可能被错误地判定为不可达——明明存在一条窄缝可以通过但因为网格太粗窄缝没有被任何格子中心点覆盖到。选得太小网格数量暴增BFS 的时间和内存都会超标。一个很实用的策略是步长取 min(机器人半径, 窄缝参考宽度) 的一个比例。做得比较稳的做法是步长取 0.5 或 0.25 倍的机器人半径。比如半径是 2步长取 1那么两堵墙之间即使只有 3 个单位的空隙也能保证至少有一列格子中心点可以穿过去。当然如果地图范围很大这个比例可能要适当放大否则格子数太多跑不动。网格的边界范围要稍微往外扩一点。如果地图本身是闭合的多边形围墙那围墙内就是可活动区域围墙外就不用管了。如果地图没有明确边界那么就需要设定一个足够大的搜索矩形确保起点和终点都在这个矩形内部并且这个矩形的边界离所有障碍物都足够远。3.2 状态定义与 BFS 流程因为 BFS 只关心能否到达所以状态非常简单就是网格坐标 (gx, gy)对应实际的圆心位置 (gx * step offsetX, gy * step offsetY)。用二维 bool 数组记录访问状态。搜索从起点对应的网格坐标开始每次尝试上下左右四个方向移动一格。移动到新格点后先检查是否越界再检查这个格点是否已经被访问过然后用之前写的 collision 函数判断这个位置是否合法。如果合法就放入队列。如果队列弹出某个格点时它对应的实际坐标离终点的实际距离小于 step / 2就认为已经到达终点附近可以判定为可达。当然更严谨的做法是在判断相邻格点可通行之后额外检查两个格点之间的连线段会不会与障碍物相交。但其实在圆形机器人的场景下只要步长足够小并且两个格点都合法那么它们之间的直线路径大概率也是安全的。严格来说两个合法点之间的线段可能擦到障碍物所以最严谨的实现是在两个格点之间做一次线段与多边形边的相交检测。不过这会显著增加计算量。在绝大多数 UVa 测试数据下仅仅依靠格点合法性判断就够了这也是比赛题目和实际工程不一样的地方。3.3 主要代码框架#include bits/stdc.h using namespace std; const double EPS 1e-9; struct Point { double x, y; }; using Polygon vectorPoint; double distToSegment(Point p, Point a, Point b) { ... } bool pointInPolygon(Point p, const Polygon poly) { ... } bool collision(Point p, const Polygon poly, double r) { ... } int main() { int n; double r, sx, sy, tx, ty; while (cin n r sx sy tx ty) { if (n 0 fabs(r) EPS) break; // 根据题目实际终止条件调整 Polygon poly(n); for (int i 0; i n; i) { cin poly[i].x poly[i].y; } Point start{sx, sy}; Point end{tx, ty}; // 检查起点终点是否合法 if (collision(start, poly, r) || collision(end, poly, r)) { cout No\n; continue; } double step r * 0.5; // 构建网格范围 double minX 1e9, maxX -1e9, minY 1e9, maxY -1e9; for (auto p : poly) { minX min(minX, p.x); maxX max(maxX, p.x); minY min(minY, p.y); maxY max(maxY, p.y); } minX - r * 3; maxX r * 3; minY - r * 3; maxY r * 3; int w (int)((maxX - minX) / step) 1; int h (int)((maxY - minY) / step) 1; vectorvectorbool vis(w, vectorbool(h, false)); queuepairint,int q; int sgx (int)((start.x - minX) / step); int sgy (int)((start.y - minY) / step); int tgx (int)((end.x - minX) / step); int tgy (int)((end.y - minY) / step); // ... BFS 主体 ... cout (reachable ? Yes : No) \n; } return 0; }上面只给出了框架。实际写的时候BFS 主体就是很标准的队列操作。这里要注意的是坐标转换的精度。用 (int)((start.x - minX) / step) 直接做强制转换可能会因为浮点误差导致索引差一。稳妥的做法是先算出一个 double 值然后加 0.5 再转 int 做四舍五入或者用int idx (int)floor(v 0.5);。我写这题的时候第一次提交错了就是因为网格索引取整的问题。在起点坐标恰好等于边界值、或者步长不能被坐标差整除的时候取整误差会让起点和终点落到错误的格子上等于还没开始搜就判错了。3.4 搜索过程的剪枝与终止条件BFS 的终止条件不能只看是否踩到了终点那个格点因为终点往往不会恰好落在格子中心。正确做法是每次从队列取出一个格点时计算该格点代表的实际位置与终点的距离如果小于等于 step * 0.707即对角线半长就可以判定到达。这个阈值的推导是这样的当前格点的搜索步长为 step它能覆盖到的实际区域是一个边长为 step 的小方格。终点在这个方格内部即视为到达。方格中心到顶点的最大距离是 step / sqrt(2)约等于 0.707 倍 step。所以只要距离小于等于 0.707 * step就说明终点一定在该格点的覆盖范围内。从另一个角度讲这个阈值也保证了搜索结果的可靠性就算存在一条更细的路径能抵达终点但这条路径在网格精度下已经无法被刻画出来了在题目评测标准里就会认为这是不可达的。这也是网格法的一个固有特性——它的结果是“在给定精度下是否存在路径”而不是“精确空间中是否存在路径”。所以如果题目对精度的要求特别高比如要求输出最短路径长度网格法就不是很合适了那种情况下应该考虑 visibility graph。但如果只是判断可达性网格法完全够用。UVa 11509 的题意我记得是判断是否可以 tour 完全部给定点或者起点到终点可达所以网格法是合适的。4. 常见问题与调试经验实录4.1 只判点、不判线导致的路径穿越网格法的最大隐患就是相邻两个合法格点之间直线连接可能与多边形相交。比如一个很窄的三角形障碍物尖角恰好戳在两个合法格点之间从格点 A 到格点 B 的连线穿过了尖角但 A 和 B 本身都不在多边形内离边的距离也都大于 r于是 BFS 就认为这条路是通的。要修复这个问题有两个方向加密网格让窄到能藏住“穿越”的缝隙不存在。但网格加密会带来性能压力。在扩展相邻格点时额外检测两个格点连线段与多边形边的相交情况。实际比赛里我通常两种都做网格步长取 r 的 0.5 倍同时在线段检测中忽略那些非常短小的边用「点到线段距离」代替「线段相交检测」也就是判断这条移动路径是否距离多边形边界太近。这样既不会太慢又能避免大部分穿越问题。4.2 起点终点的合法性校验遗漏另一个特别常见的坑只对搜索过程中的格点做碰撞检测却忘了在最开始检查起点和终点本身是否合法。如果起点本身就在障碍物内部或者起点离墙太近那根本不需要搜索直接输出不可达。很多人写代码的时候BFS 里的 collision 是每次扩展时调用的起点被塞进队列时可能绕过了检查于是起点不合法的问题就会在输出阶段暴露出来。更隐蔽的情况是终点不合法BFS 都搜到了终点旁边结果发现终点实际位置离墙太近机器人停不下来。这种问题在大的测试数据里很容易被忽略因为表面上看搜索结果是“可到达”但实际上终点位置是不允许机器人存在的。我的习惯是在程序一开始就做一次起点和终点的合法性检查并且一旦不合法就立刻输出结果跳过后续所有逻辑。这个习惯让我在很多几何搜索题里省下了大量的 debug 时间。4.3 多边形顺序与闭合处理UVa 里给的多边形顶点有时候是顺时针有时候是逆时针而且题面不一定说明。上面提到的 pointInPolygon 射线法对顺序不敏感所以这点我们可以放一半的心。但处理多边形的边时要注意最后一条边需要从最后一个顶点回到第一个顶点也就是多边形的闭合边。很多人在遍历边时只处理了 poly[i] 到 poly[i1]漏掉了最后一条闭合边导致机器人可以从“最后一条边”穿过去而不被检测到。正确的遍历方式是用模运算for (int i 0; i n; i) { int j (i 1) % n; // 处理 poly[i] 到 poly[j] 的边 }这是一个非常低级的错误但在我帮别人 review 几何题代码时经常看到。漏掉闭合边的代码在大多数测试用例里都能通过因为大部分路线不会刻意从最后一条边穿墙但一旦评测数据里出现了针对性的 case就会 WA 得莫名其妙。4.4 浮点精度与判题系统的 EPS 博弈UVa 的几何题输出一般比较宽松只要不是差得离谱都能过。但判断是否可达的题最怕的就是把“边界相切”判成“碰撞”。比如机器人的圆的边缘刚好贴着多边形的一条边过去。数学上这是合法的但用 double 计算时距离可能算出来是 r 2e-16也可能算出来是 r - 2e-16取决于中间运算的舍入方向。如果你把条件写成d r那么 2e-16 的误差可能让你误判。解决方案就是加 EPS。我一般用d r - EPS来判断碰撞其中 EPS 1e-9。这样既不会把明显穿墙的情况放过去也不会因为 1e-15 的浮点噪音导致误判。如果你的代码用了大量的乘法和开方累积误差可能会到 1e-8 左右这时候 EPS 取 1e-9 可能反而太紧可以根据实测调整到 1e-7。需要特别注意的是EPS 不能设置得太大。有些题目里机器人半径可能只有 0.01窄缝宽度也只有 0.02如果你把 EPS 设成 1e-3那机器人的有效半径相当于变大了 0.001虽然绝对值不大但相对误差会高达 100%本来能过的窄缝也过不去了。4.5 BFS 队列爆炸与性能优化网格步长设置不合理时BFS 的搜索空间会急剧膨胀。假设地图范围是 1000 × 1000机器人半径 r 是 2步长取 0.5那么网格规模是 2000 × 2000也就是 400 万个格点。对于 BFS 来说400 万个点的访问状态存储需要 4 MB 左右用 bitset 更少队列操作也是百万量级的跑起来大概要零点几秒到一两秒在 UVa 的时间限制下通常能过但已经不算富余了。如果步长取 0.25网格数变成 1600 万个内存和耗时都会明显增加可能就会超时。所以步长不是越细越好。我的建议是先看清楚数据范围如果地图面积大步长就取 r 的 0.5 到 1.0 倍如果地图面积小可以取 r 的 0.25 到 0.5 倍。不要一上来就追求最精细的网格比赛里时间也是资源。如果发现 BFS 跑得太慢还有一个优化方向不必对全部四个方向都做 collision 检测。可以在入队之前先判断目标格点与当前格点之间是否经过同一块区域如果距离都很短多数情况下二者合法性相同可以简化成只检测目标格点的合法性。当然这只是一种加速 trick不要影响正确性。4.6 从 WA 到 AC 的排查记录我第一次提交这题的时候WA 了大概三次。第一次是闭合边漏处理第二次是起点没做合法性检查第三次是步长取太大导致一个窄通道没有被网格覆盖到。第三次那个问题最隐蔽。当时我取的步长是 r × 1.5理由是想加快搜索速度。结果题目里有一条很窄的通道宽度大概是 2.1 倍的 r按道理机器人是能通过的。但因为步长太大通道两边的墙距离太近网格中心点要么落在左边墙的碰撞范围内要么落在右边墙的碰撞范围内没有任何一个网格中心点落在通道中间的安全区域里。网格法就这样把一个真实可通的路径过滤掉了。后来我把步长改成了 r × 0.5这个问题就消失了。所以这里也给大家一个参考如果你用网格法做几何避障题网格间距最好不要超过最小通道宽度的一半。如果你无法预知最小通道宽度那就按 r 的比例来经验值 0.5 倍 r 是比较稳妥的。5. 从这道题能带走的算法思维Touring Robot 这种题目表面上是机器人路径规划背后考察的是两个计算几何领域最核心的思想一是“圆缩点障碍外扩”的空间变换二是“连续空间离散化”后的搜索策略。这两个思想往大了说可以延伸到无人车路径规划里的配置空间Configuration Space概念往小了说就是每次做机器人模拟题时最常用的套路。我在实际做题的时候遇到圆形机器人的问题第一反应一定是先做空间变换把机器人变成点。这几乎是刻在 DNA 里的操作。因为你一旦把一个复杂的碰撞问题化简成点与多边形的距离问题后面不管是做 BFS、A*还是 visibility graph都会变得非常清晰。另外很多初学者会觉得这种题很难是因为他们把几何问题和搜索问题割裂开了。实际上这两个领域经常是组合出现的。BFS 负责搜索几何计算负责判断状态合法性两者通过一组合法的状态转移函数连接在一起。在 UVa 11509 里这个转移函数就是 collision 函数。把转移函数写对、写稳整个题就完成了一大半。如果你以前没有把“BFS 几何合法性判断”这种套路当回事我建议你从这道题开始把它作为一个模板题总结进自己的代码库。以后遇到类似“圆在障碍物间移动”的题目直接把模板拎出来改改边界条件就能用效率会高很多。最后再分享一个小技巧做这类几何搜索题千万不要一上来就写完整代码。先在纸上画出几个典型场景比如“宽通道”“窄通道”“尖角障碍”“凹多边形陷阱”然后手动模拟一下你的搜索算法在这些场景下是怎么工作的把潜在的问题扼杀在写代码之前。这样做的成本很低但能避免大量的无效调试时间。