题目;http://poj.org/problem?id=3182
题意:一个棋盘中间有一个联通块,给你一个起点让你从起点开始绕联通块外围一圈并回到起点,求最小步数。
分析:
首先根据数据的范围比较小,所以觉得应该是搜索,而且是BFS。
朴素的想法是从起点开始BFS 8个方向扩展,不过这样肯定要跪。
注意到这个题目的特点:路径要围一个联通块,而我们一般做的BFS是从一个起点到终点,这之间可以转化吗?
当然可以,围起联通块相当于从联通块边界上一点出发向两边BFS到起点!!!!!
具体实现的话,可以取联通块右边界的一条线段,然后枚举上面所有点,向两边BFS(舍弃一个方向)。
总结:
BFS处理围一个图形的问题可以转化成图形上一点向两边BFS到起点