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

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

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

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

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

1    void look()
2    {
3	cout<<"x:"<<x-C<<" y:"<<y-C<<" d:"<<d<<endl;
4    }
5}s,tar;
6int n;

 1void bfs()
 2{
 3    queue<node>q;
 4    s.x = 500;
 5    s.y = 500;
 6    s.d = 0;
 7    vis[500][500] = true;
 8    q.push(s);
 9    while (!q.empty())
10    {
11	node pre = q.front() ;q.pop();
12//	pre.look();
13	if (pre.x==tar.x&&pre.y==tar.y)
14	{
15	    cout<<pre.d<<endl;
16	    return ;
17	}

 1	for ( int i = 0 ; i < 4 ; i++)
 2	{
 3	    node nxt;
 4	    nxt.x = pre.x + dx4[i];
 5	    nxt.y = pre.y + dy4[i];
 6	    nxt.d = pre.d + 1;
 7	    if (nxt.ok())
 8	    {
 9		q.push(nxt);
10		vis[nxt.x][nxt.y] = true;
11	    }
12	}
13    }
14}
15int main()
16{
17	#ifndef  ONLINE_JUDGE 
18	freopen("code/in.txt","r",stdin);
19  #endif

1	cin>>tar.x>>tar.y>>n;
2	tar.x+=C;
3	tar.y+=C;

1	ms(vis,false);
2	for ( int i = 1 ; i <= n ; i++)
3	{
4	    int u,v;
5	    cin>>u>>v;
6	    u+=C;
7	    v+=C;
8	    vis[u][v] = true;
9	}

	bfs();

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}