首页 > 代码库 > [USACO2006][poj3182]The Grove(巧妙的BFS)

[USACO2006][poj3182]The Grove(巧妙的BFS)

题目;http://poj.org/problem?id=3182

题意:一个棋盘中间有一个联通块,给你一个起点让你从起点开始绕联通块外围一圈并回到起点,求最小步数。

分析:

首先根据数据的范围比较小,所以觉得应该是搜索,而且是BFS。

朴素的想法是从起点开始BFS 8个方向扩展,不过这样肯定要跪。

注意到这个题目的特点:路径要围一个联通块,而我们一般做的BFS是从一个起点到终点,这之间可以转化吗?

当然可以,围起联通块相当于从联通块边界上一点出发向两边BFS到起点!!!!!

具体实现的话,可以取联通块右边界的一条线段,然后枚举上面所有点,向两边BFS(舍弃一个方向)。

总结:

BFS处理围一个图形的问题可以转化成图形上一点向两边BFS到起点