描述


http://www.lydsy.com/JudgeOnline/problem.php?id=1627

网格图,给出起点,终点,障碍,求最短路.

分析


简单的宽搜.

 #include <bits/stdc++.h>
using namespace std;
inline int read(int &x){x=;int k=;char c;for(c=getchar();c<''||c>'';c=getchar())if(c=='-')k=-;for(;c>=''&&c<='';c=getchar())x=x*+c-'';return x*=k;} const int maxn=+;
int n,x,y;
int go[][]={,,,-,,,-,};
bool mark[maxn][maxn];
struct node{
int x,y,t;
node(){}
node(int x,int y,int t):x(x),y(y),t(t){}
}q[maxn*maxn];
inline void bfs(){
int L,R;
q[L=R=]=node(,,);
while(L<=R){
node t=q[L++];
for(int i=;i<;i++){
int tx=t.x+go[i][],ty=t.y+go[i][];
if(tx>=&&tx<=&&ty>=&&ty<=&&!mark[tx][ty]){
if(tx==x+&&ty==y+){ printf("%d\n",t.t+); return; }
mark[tx][ty]=true;
q[++R]=node(tx,ty,t.t+);
}
}
}
}
int main(){
read(x); read(y); read(n);
for(int i=,tx,ty;i<=n;i++){
read(tx); read(ty);
mark[tx+][ty+]=true;
}
bfs();
return ;
}

1627: [Usaco2007 Dec]穿越泥地

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 659  Solved: 436
[Submit][Status][Discuss]

Description


早6:00,Farmer
John就离开了他的屋子,开始了他的例行工作:为贝茜挤奶。前一天晚上,整个农场刚经受过一场瓢泼大雨的洗礼,于是不难想见,FJ
现在面对的是一大片泥泞的土地。FJ的屋子在平面坐标(0, 0)的位置,贝茜所在的牛棚则位于坐标(X,Y) (-500 <= X <=
500; -500 <= Y <= 500)处。当然咯, FJ也看到了地上的所有N(1 <= N <=
10,000)个泥塘,第i个泥塘的坐标为 (A_i, B_i) (-500 <= A_i <= 500;-500 <= B_i
<= 500)。每个泥塘都只占据了它所在的那个格子。 Farmer
John自然不愿意弄脏他新买的靴子,但他同时想尽快到达贝茜所在的位置。为了数那些讨厌的泥塘,他已经耽搁了一些时间了。如果Farmer John
只能平行于坐标轴移动,并且只在x、y均为整数的坐标处转弯,那么他从屋子门口出发,最少要走多少路才能到贝茜所在的牛棚呢?你可以认为从FJ的屋子到牛
棚总是存在至少一条不经过任何泥塘的路径。

Input

* 第1行: 3个用空格隔开的整数:X,Y 和 N

* 第2..N+1行: 第i+1行为2个用空格隔开的整数:A_i 和 B_i

Output

* 第1行: 输出1个整数,即FJ在不踏进泥塘的情况下,到达贝茜所在牛棚所需要 走过的最小距离

Sample Input

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2

输入说明:

贝茜所在牛棚的坐标为(1, 2)。Farmer John能看到7个泥塘,它们的坐标分
别为(0, 2)、(-1, 3)、(3, 1)、(1, 1)、(4, 2)、(-1, 1)以及(2, 2)。
以下为农场的简图:(*为FJ的屋子,B为贝茜呆的牛棚)

4 . . . . . . . .
3 . M . . . . . .
Y 2 . . M B M . M .
1 . M . M . M . .
0 . . * . . . . .
-1 . . . . . . . .
-2-1 0 1 2 3 4 5

X

Sample Output

11

HINT

    约翰的最佳路线是:(0,0),(一1,0),(一2,0),(一2,1),(一2,2),(一2,3),(一2,4),(一1,4),(0,4),  (0,3),  (1,3),  (1,2).

Source

最新文章

  1. Xamarin 免费了,你能做什么?
  2. sql 查询
  3. Python爬虫Scrapy框架入门(1)
  4. Java连接MongoDB进行增删改查
  5. iOS button 里边的 字体的 摆放
  6. Linux常用命令_(备份压缩)
  7. JavaScript算法题之–随机数的生成
  8. response 后刷新页面,点击按钮后,禁用该按钮
  9. 轻松搭建自己的Linux发行版本
  10. tpl demo
  11. python一些技巧
  12. 关于PHP伪静态Rewrite设置
  13. N个数依次入栈,出栈顺序有多少种
  14. MBG 相关资源链接
  15. spark集群安装配置
  16. js call方法
  17. 配置maven项目的开发时的默认jdk版本
  18. linux显示完整目录
  19. German Collegiate Programming Contest 2013-B:Booking(贪心)
  20. Python词云(词频统计,掩膜显示)

热门文章

  1. Android-Empty-Layout:展示不同类型的页面布局,用于视图是空的时候
  2. SecureCRT配色方案
  3. 1515 跳 - Wikioi
  4. 【BZOJ】【2982】Combination
  5. nenu contest2
  6. 【ACMER纷纷表示】女生应该找一个玩ACM的男生
  7. 11 个最佳 jQuery 滚动条插件
  8. 如何处理JSON中的特殊字符
  9. 分享一个安装PE到硬盘的软件
  10. lintcode 中等题:subsets II 带重复元素的子集