[USACO07DEC]Mud Puddles S-Toy模板网

这篇具有很好参考价值的文章主要介绍了[USACO07DEC]Mud Puddles S。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

[USACO07DEC]Mud Puddles S

题目描述

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 all N (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.

清早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的屋子到牛棚总是存在至少一条不经过任何泥塘的路径。

输入格式

* Line 1: Three space-separate integers: X, Y, and N.

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

* Lines 2..N+1: Line i+1 contains two space-separated integers: Ai and Bi

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

输出格式

* Line 1: The minimum distance that Farmer John has to travel to reach Bessie without stepping in mud.文章来源地址https://www.toymoban.com/news/detail-427285.html

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

样例

样例输入

样例输出

代码

#include <bits/stdc++.h>
using namespace std;
struct Node{
	int x,y,dis;
};
queue<Node> q;
bool m[1001][1001];
int x,y,n;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
bool f(int x,int y)
{
	return x<-500||x>500||y<-500||y>500||m[x+500][y+500];
}
void bfs()
{
	q.push({0,0,0});
	while(!q.empty())
	{
		int nx=q.front().x,ny=q.front().y,val=q.front().dis;
		q.pop();
		if(f(nx,ny)) continue;
		m[nx+500][ny+500]=1;
		if(nx==x&&ny==y)
		{
			cout << val << endl;
			return;
		}
		for(int i=0;i<4;i++)
		{
			q.push({nx+dx[i],ny+dy[i],val+1});
		}
	}
}
int main()
{
	cin >> x >> y >> n;
	while(n--)
	{
		int X,Y;
		cin >> X >> Y;
		m[X+500][Y+500]=1;
	}
	bfs();
	return 0;
}

到了这里，关于[USACO07DEC]Mud Puddles S的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！