| 题目名称 | 152. [USACO Dec07] 泥潭 |
|---|---|
| 输入输出 | mud.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 BYVoid
于2008-10-06加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：108， 提交：226， 通过率：47.79% | ||||
 Hzoi_Queuer |
100 | 0.000 s | 0.00 MiB | C++ |
 槿柒 |
100 | 0.000 s | 0.00 MiB | C++ |
 城南花已开 |
100 | 0.003 s | 2.61 MiB | C++ |
 HanksonChristall |
100 | 0.026 s | 2.00 MiB | C++ |
 Ostmbh |
100 | 0.026 s | 2.00 MiB | C++ |
 Farmer_Joe |
100 | 0.026 s | 11.74 MiB | C++ |
|
城南花已开 |
100 | 0.029 s | 10.42 MiB | C++ |
 0 |
100 | 0.030 s | 1.27 MiB | C++ |
 zjmfrank2012 |
100 | 0.030 s | 2.22 MiB | C++ |
 苏轼 |
100 | 0.031 s | 1.27 MiB | C++ |
| 本题关联比赛 | |||
| 20181007 | |||
| 关于 泥潭 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
成功题解：https://ycwy-zd-rz.blog.luogu.org/cogs152-post
其实就是一道bfs水题，加了freopen后基本上都会过. [cpp]#include<bits/stdc++.h> using namespace std; #define s freopen("mud.in","r",stdin) #define ss freopen("mud.out","w",stdout) #define sss fclose(stdin) #define ssss fclose(stdout) #define mint int// long #define pd if(nx<=maxx && ny<=maxx && nx>=0 && ny>=0 && !mp[nx][ny]) mint mp[1010][1010]; mint rock,ax,ay; mint maxx=1010; mint hd,tl; mint dx[]={0,0,0,1,-1}; mi[][/cpp] | ||||
|
hh
 dududu
2018-10-10 18:54
3楼
| ||||
|
x,y,n读反了= =
 | ||||
|
裸BFS。用数组a（bool）标记一个格子是否能走。一个格子可以走当且仅当它不是泥潭且没有被走过。
 赵寒烨
2013-08-26 23:19
1楼
| ||||
U.N.A
HouJikan【题目描述】
Farmer John在早晨6点准时去给贝茜挤奶，然而昨天晚上下了大雨，他的牧场变得泥泞不堪了。Farmer John的家在坐标平面的 (0,0) 处，贝茜在 (X, Y) (-500 ≤ X ≤ 500; -500 ≤ Y ≤ 500)。他看见了所有的 N (1 ≤ N ≤ 10,000) 个泥潭，分别在 (Ai, Bi) (-500 ≤ Ai ≤ 500; -500 ≤ Bi ≤ 500) 。每个泥潭只占一个点的位置。
Farmer John 刚刚买了新的靴子，他绝对不想把靴子踩进泥潭弄脏，而他又想尽快的找到贝茜。他已经快晚了，因为他花了大量的时间来找到所有的泥潭的位置。 Farmer John 只能平行于坐标轴移动，每次移动一个单位。请你帮助 Farmer John 找到一条路，使得 Farmer John 能够最快的找到贝茜，而且不会弄脏靴子。我们约定一定存在一条路使 Farmer John 找到贝茜。
【输入格式】
第 1 行: 三个整数 X, Y, N
第 2..N+1 行: 第 i+1 行 包含两个整数 Ai , Bi
【输出格式】
第 1 行: Farmer John 能够最快的找到贝茜，而且不会弄脏靴子，要走的最小的距离。
【输入样例】
1 2 7 0 2 -1 3 3 1 1 1 4 2 -1 1 2 2
【输出样例】
11