BZOJ 1627: [Usaco2007 Dec]穿越泥地 (BFS)

Apr 4, 2016 · 2 min read · bfs

1627: [Usaco2007 Dec]穿越泥地

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 624  Solved: 411 [Submit][Status][Discuss]

Description

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

Input

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

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

Output

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

Sample Input

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

输入说明:

贝茜所在牛棚的坐标为(1, 2)。Farmer John能看到7个泥塘，它们的坐标分 别为(0, 2)、(-1, 3)、(3, 1)、(1, 1)、(4, 2)、(-1, 1)以及(2, 2)。 以下为农场的简图：（*为FJ的屋子，B为贝茜呆的牛棚）

4 . . . . . . . . 3 . M . . . . . . Y 2 . . M B M . M . 1 . M . M . M . . 0 . . * . . . . . -1 . . . . . . . . -2-1 0 1 2 3 4 5

X

Sample Output

11

HINT

    约翰的最佳路线是：(0，0)，（一1，0），（一2，0），（一2，1），（一2，2），（一2，3），（一2，4），（一1，4），(0,4),  (0,3),  (1,3),  (1,2).

思路：bfs,坐标有负数，整体平移500即可。

/* ***********************************************
Author :111qqz
Created Time :2016年04月04日 星期一 14时43分48秒
File Name :code/bzoj/1627.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E4+7;
const int C =500;
bool vis[1005][1005];
struct node
{
    int x,y;
    int d;

    bool ok ()
    {
	if (x>=0&&x<=1000&&y>=0&&y<=1000&&!vis[x][y]) return true;
	return false;
    }

    void look()
    {
	cout<<"x:"<<x-C<<" y:"<<y-C<<" d:"<<d<<endl;
    }
}s,tar;
int n;


void bfs()
{
    queue<node>q;
    s.x = 500;
    s.y = 500;
    s.d = 0;
    vis[500][500] = true;
    q.push(s);
    while (!q.empty())
    {
	node pre = q.front() ;q.pop();
//	pre.look();
	if (pre.x==tar.x&&pre.y==tar.y)
	{
	    cout<<pre.d<<endl;
	    return ;
	}
	
	
	for ( int i = 0 ; i < 4 ; i++)
	{
	    node nxt;
	    nxt.x = pre.x + dx4[i];
	    nxt.y = pre.y + dy4[i];
	    nxt.d = pre.d + 1;
	    if (nxt.ok())
	    {
		q.push(nxt);
		vis[nxt.x][nxt.y] = true;
	    }
	}
    }
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif

	cin>>tar.x>>tar.y>>n;
	tar.x+=C;
	tar.y+=C;


	ms(vis,false);
	for ( int i = 1 ; i <= n ; i++)
	{
	    int u,v;
	    cin>>u>>v;
	    u+=C;
	    v+=C;
	    vis[u][v] = true;
	}

	bfs();


  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}