【BZOJ1627】[Usaco2007 Dec]Mud Puddles 穿越泥地

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

11

Silver

BZOJ 1627

代码 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;
}``````