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

2016-04-04 · 3 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

Sample Output

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即可。

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年04月04日 星期一 14时43分48秒
  4File Name :code/bzoj/1627.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=1E4+7;
 34const int C =500;
 35bool vis[1005][1005];
 36struct node
 37{
 38    int x,y;
 39    int d;
 40
 41    bool ok ()
 42    {
 43	if (x>=0&&x<=1000&&y>=0&&y<=1000&&!vis[x][y]) return true;
 44	return false;
 45    }
 46
 47    void look()
 48    {
 49	cout<<"x:"<<x-C<<" y:"<<y-C<<" d:"<<d<<endl;
 50    }
 51}s,tar;
 52int n;
 53
 54
 55void bfs()
 56{
 57    queue<node>q;
 58    s.x = 500;
 59    s.y = 500;
 60    s.d = 0;
 61    vis[500][500] = true;
 62    q.push(s);
 63    while (!q.empty())
 64    {
 65	node pre = q.front() ;q.pop();
 66//	pre.look();
 67	if (pre.x==tar.x&&pre.y==tar.y)
 68	{
 69	    cout<<pre.d<<endl;
 70	    return ;
 71	}
 72
 73
 74	for ( int i = 0 ; i < 4 ; i++)
 75	{
 76	    node nxt;
 77	    nxt.x = pre.x + dx4[i];
 78	    nxt.y = pre.y + dy4[i];
 79	    nxt.d = pre.d + 1;
 80	    if (nxt.ok())
 81	    {
 82		q.push(nxt);
 83		vis[nxt.x][nxt.y] = true;
 84	    }
 85	}
 86    }
 87}
 88int main()
 89{
 90	#ifndef  ONLINE_JUDGE 
 91	freopen("code/in.txt","r",stdin);
 92  #endif
 93
 94	cin>>tar.x>>tar.y>>n;
 95	tar.x+=C;
 96	tar.y+=C;
 97
 98
 99	ms(vis,false);
100	for ( int i = 1 ; i <= n ; i++)
101	{
102	    int u,v;
103	    cin>>u>>v;
104	    u+=C;
105	    v+=C;
106	    vis[u][v] = true;
107	}
108
109	bfs();
110
111
112  #ifndef ONLINE_JUDGE  
113  fclose(stdin);
114  #endif
115    return 0;
116}