http://poj.org/problem?id=3626
Mud Puddles
Time Limit:1000MS |
|
Memory Limit:65536K |
|
|
|
Description
Farmer John is leaving his house promptly at 6 AM for his daily milking of Bessie. However, the previous evening saw a heavy rain, and the fields are quite muddy. FJ starts at the point (0, 0) in the coordinate plane and heads toward Bessie who is located at (X,Y) (-500 ≤X≤ 500; -500 ≤Y≤ 500). He can see allN(1 ≤N≤ 10,000) puddles of mud, located at points (Ai,Bi) (-500 ≤Ai≤ 500; -500 ≤Bi≤ 500) on the field. Each puddle occupies only the point it is on.
Having just bought new boots, Farmer John absolutely does not want to dirty them by stepping in a puddle, but he also wants to get to Bessie as quickly as possible. He's already late because he had to count all the puddles. If Farmer John can only travel parallel to the axes and turn at points with integer coordinates, what is the shortest distance he must travel to reach Bessie and keep his boots clean? There will always be a path without mud that Farmer John can take to reach Bessie.
Input
* Line 1: Three space-separate integers:X,Y, andN.
* Lines 2..N+1: Linei+1 contains two space-separated integers:AiandBi
Output
* Line 1: The minimum distance that Farmer John has to travel to reach Bessie without stepping in mud.
Sample Input
1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2
Sample Output
11
分享到:
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
北大POJ中级搜索全部练习【解题报告+AC代码】
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ初级-简单搜索 解题报告+AC代码
算法入门—广度优先搜索—raphealguo
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
简单搜索题 数独 答案 POJ 2676 也可以没事玩玩数独。
poj 1084 Square Destroyer 的AC代码 深度优先搜索 + 启发 未用跳舞链
相信坦克大战大家都玩过吧,本题就是根据这个游戏设计的。坦克要从起点(Y),到...本题可以使用改进过的广搜或优先队列+bfs 或 记忆化广搜三种方法来解决。第一种方法:改进过的BFS:有些节点需要耗费2个单位时间,要
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
供初学编程基本算法的人练习使用,在poj.grids.cn上
POJ 3131 双向BFS解立体八数码问题
NULL 博文链接:https://128kj.iteye.com/blog/1707218
poj分类poj分类poj分类poj分类
NULL 博文链接:https://128kj.iteye.com/blog/1740501
北大POJ1159-Palindrome 解题报告+AC代码