题目描述：
干了一整天的活，农夫约翰完全忘记了他把拖拉机落在田地中央了。
他的奶牛非常调皮，决定对约翰来场恶作剧。
她们在田地的不同地方放了 $ N $ 捆干草，这样一来，约翰想要开走拖拉机就必须先移除一些干草捆。
拖拉机的位置以及 $ N $ 捆干草的位置都是二维平面上的整数坐标点。
拖拉机的初始位置上没有干草捆。
当约翰驾驶拖拉机时，他只能沿平行于坐标轴的方向（北，南，东和西）移动拖拉机，并且拖拉机必须每次移动整数距离。
例如，驾驶拖拉机先向北移动 $ 2 $ 单位长度，然后向东移动 $ 3 $ 单位长度。
拖拉机无法移动到干草捆占据的位置。
请帮助约翰确定他需要移除的干草捆的最小数量，以便他能够将拖拉机开到二维平面的原点。
输入格式
第一行包含三个整数： $ N $ 以及拖拉机的初始位置 $ (x,y) $ 。
接下来 $ N $ 行，每行包含一个干草捆的位置坐标 $ (x,y) $ 。
输出格式
输出约翰需要移除的干草捆的最小数量。
数据范围
$ 1\le N \le 50000,1 \le x,y \le 1000 $
输入样例：
1
2
3
4
5
6
7
8
| 7 6 3
6 2
5 2
4 3
2 1
7 3
5 4
6 4
|
输出样例：
题解：
可以走在图的外侧。
图中权重为 $ 0 $ 和 $ 1 $ ，因此可以考虑使用双端队列搜索。使用一般的 bfs 不能求出结果。
双端队列求最短路：
把扩展的权重为 $ 0 $ 的放在队首，把扩展的权重为 $ 1 $ 的放在队尾。整个队列始终保持前半部分比后半部分小 $ 1 $ 。松弛操作按照 Dijkstra 中的操作一样，这样的话终点第一次出队时（即加入已扩展队列时）就得到了最短路。
因为本题目可以走在图的外侧，所以需要把图的范围搞大一点，搞成 $ [0, 1001] $ ，把原数据给框住，这样的话最后走边界就可以得到答案。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int g[maxn][maxn];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int sx, sy;
bool vis[maxn][maxn];
int dis[maxn][maxn];
int bfs()
{
memset(dis, 0x3f, sizeof(dis));
deque<pair<int, int>> q;
q.push_back({sx, sy});
dis[sx][sy] = 0;
while (!q.empty())
{
auto out = q.front();
q.pop_front();
if (vis[out.first][out.second])
continue;
vis[out.first][out.second] = true;
if (out.first == 0 && out.second == 0)
break;
for (int i = 0; i < 4; i++)
{
int newx = out.first + dx[i];
int newy = out.second + dy[i];
if (newx < 0 || newx > 1001 || newy < 0 || newy > 1001)
continue;
int w = 0;
if (g[newx][newy])
w = 1;
if (dis[newx][newy] > dis[out.first][out.second] + w)
{
dis[newx][newy] = dis[out.first][out.second] + w;
if (w)
q.push_back({newx, newy});
else
q.push_front({newx, newy});
}
}
}
return dis[0][0];
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
read(n, sx, sy);
int x, y;
while (n--)
{
read(x, y);
g[x][y] = 1;
}
cout << bfs() << endl;
return 0;
}
|