描述 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 的屋子到牛棚总是存在至少一条不经过任何泥塘的路径。
输入格式 InputFormat
第 1 行: 3 个用空格隔开的整数：X，Y 和 N.
第 2..N+1 行: 第 i+1 行为 2 个用空格隔开的整数：A_i 和 B_i.
输出格式 OutputFormat
第 1 行: 输出 1 个整数，即 FJ 在不踏进泥塘的情况下，到达贝茜所在牛棚所需要 走过的最小距离
样例输入 SampleInput
10 -1 50
5 5
4 10
5 -3
-9 -9
-8 -1
-1 -9
-6 -9
-8 -7
-10 9
8 -5
-6 -5
5 10
3 -9
-9 0
-3 -7
-6 -2
8 2
5 -8
-7 9
-3 8
7 -7
4 4
-8 8
3 -1
1 -9
10 2
3 -9
-7 7
0 10
-3 -3
2 -9
3 -7
-4 9
7 5
-2 8
-10 9
-10 -5
-1 6
0 4
-4 8
1 6
-10 -7
6 -5
-7 -5
-1 -2
3 -3
2 -5
2 2
-10 -5
-4 -8
样例输出 SampleOutput
11
来源 Source
Silver
代码 Code
BFS.
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define b(i,j) B[i+500][j+500]
const int dx[5]={0,0,0,1,-1};
const int dy[5]={0,1,-1,0,0};
struct point
{
int z,y,x;
}f[1000005];
bool B[1005][1005];
int i,j,t,n,m,l,r,k,ex,ey,ans;
void bfs()
{
int i,j,t,tx,ty;
l=r=0;f[l].x=0;f[l].y=0;f[l].z=0;
while (r>=l)
{
if (f[l].x==ex && f[l].y==ey)
{
ans=f[l].z;
return ;
}
for (i=1;i<=4;i++)
{
tx=f[l].x+dx[i];ty=f[l].y+dy[i];
if (tx<-500 || tx>500 || ty<-500 || ty>500) continue;
if (b(tx,ty)==false) continue;
f[++r].x=tx;f[r].y=ty;f[r].z=f[l].z+1;
b(tx,ty)=false;
}
l++;
}
}
int main()
{
scanf("%d%d%d",&ex,&ey,&n);
memset(B,true,sizeof(B));
for (i=1;i<=n;i++)
{
scanf("%d%d",&l,&r);
b(l,r)=false;
}
ans=0;
bfs();
printf("%dn",ans);
return 0;
}