题解：洛谷 P2873 [USACO07DEC] Mud Puddles S

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P2873 [USACO07DEC] Mud Puddles S – 洛谷

【题目描述】

农夫约翰在早上

6

6

6 点准时离开家去挤奶贝茜。然而，前一天晚上下了大雨，田地里非常泥泞。约翰从坐标平面上的点

(

0

,

0

)

(0,0)

(0,0) 出发，前往位于

(

X

,

Y

)

(X,Y)

(X,Y) 的贝茜（

−

500

≤

X

≤

500

-500\\le X\\le 500

−500≤X≤500；

−

500

≤

Y

≤

500

-500\\le Y\\le 500

−500≤Y≤500）。他可以看到田地上所有

N

(

1

≤

N

≤

10

,

000

)

N(1\\le N\\le 10,000)

N(1≤N≤10,000) 个泥坑，位于点

(

A

i

,

B

i

)

(A_i,B_i)

(Ai​,Bi​)（

−

500

≤

A

i

≤

500

-500\\le A_i\\le 500

−500≤Ai​≤500；

−

500

≤

B

i

≤

500

-500\\le B_i\\le 500

−500≤Bi​≤500）。每个泥坑只占据它所在的点。

刚买了新靴子的农夫约翰绝对不想弄脏他的靴子，但他也想尽快到达贝茜。他已经迟到了，因为他不得不数清所有的泥坑。如果农夫约翰只能平行于坐标轴行走，并且只能在整数坐标点处转弯，那么他到达贝茜并保持靴子干净的最短距离是多少？总会有一条没有泥的路径可以让农夫约翰到达贝茜。

【输入】

• 第 $1$
• 第 $2$

【输出】

• 第 $1$

【输入样例】

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

【输出样例】

11

【核心思想】

【解题思路】

【算法标签】

#普及- #BFS-二维

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, sx, sy, minx=1e9, miny=1e9, maxx=–1e9, maxy=–1e9, dx[4]={–1,1,0,0}, dy[4]={0,0,–1,1}, tx, ty, tstep;
int a[1005][1005]={0}, vis[1005][1005]={0};
struct node {
int x, y, step, visit;
};
int main()
{
cin >> sx >> sy >> n; // 输入结束坐标及n
for (int i=1; i<=n; i++) { // 遍历n个泥塘坐标
int tmp1, tmp2;
cin >> tmp1 >> tmp2; // 输入坐标
minx = min(minx, tmp1+500); // 计算x坐标最小值
maxx = max(maxx, tmp1+500); // 计算x坐标最大值
miny = min(miny, tmp2+500); // 计算y坐标最小值
maxy = max(maxy, tmp2+500); // 计算y坐标最大值
a[tmp1+500][tmp2+500]=1; // 因为存在负数，x和y均加上500，对于泥塘的坐标，a数组置为1
}
minx = min(minx, 500); // 再与(0,0)（即(500,500））进行比较
maxx = max(maxx, 500);
miny = min(miny, 500);
maxy = max(maxy, 500);
queue<node> q; // 定义队列
node tp = {500, 500, 0}; // 队头数据
q.push(tp); // 压入队列
while (!q.empty()) { // bfs模板
tp = q.front();
q.pop();
for (int i=0; i<4; i++) { // 进行上下左右位置移动
tx = tp.x + dx[i];
ty = tp.y + dy[i];
tstep = tp.step+1; // 每移动一个格子，step加1
if (tx<minx–1||tx>maxx+1||ty<miny–1||ty>maxy+1) continue; // 当移动后的坐标越界时，继续循环
if (tx==sx+500 && ty==sy+500) { // 当遇到终点时，打印step，退出循环
cout << tstep << endl;
return 0;
}
if (a[tx][ty]==0 && vis[tx][ty]==0) { // 将要移动的坐标不是泥塘，且没有访问过
vis[tx][ty]=1; // 更新vis数组
node t = {tx, ty, tstep}; // 初始化t节点
q.push(t); // 将其压入队列中
}
}
}

return 0;
}

【运行结果】

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