[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.

第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;
}

本文來自小默的博客，轉載請注明原文鏈接：https://www.cnblogs.com/momotrace/p/p2873.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/551417.html

標籤：C

上一篇：行程

下一篇：返回列表