F. Mud Puddles

题目链接：

题目：

农夫约翰早上6点离开家，每天挤奶贝西。然而，前一天晚上看到一场大雨，田野非常泥泞。 FJ从坐标平面中的点（0,0）开始，朝向位于（X，Y）的Bessie（-500≤X≤500;-500≤Y≤500）。他可以看到所有N（1≤N≤10,000）泥浆的水坑，位于油田的点（Ai，Bi）（-500≤Ai≤500;-500≤Bi≤500）。每个水坑只占据它所在的点。

刚刚买了新靴子，Farmer John绝对不想踩到水坑弄脏他们，但他也希望尽快到达Bessie。他已经迟到了，因为他不得不算上所有的水坑。如果Farmer John只能平行于轴行进并转向带有整数坐标的点，那么他必须前往Bessie并保持靴子清洁的最短距离是多少？ Farmer John可以带着一条没有泥浆的路径到达Bessie。

输入描述：

*第1行：三个空格分隔的整数：X，Y和N.

*行2..N 1：行i 1包含两个空格分隔的整数：Ai和Bi

输出描述：

*第1行：Farmer John必须前往Bessie而不踩泥的最小距离。

思路：BFS宽搜，稍微变化一下，由于坐标存在负值将起始点变为（500,500）

越界条件变为<0||>1000，终点变为X+500,Y+500,将1000*1000的矩阵初始化为0，然后有泥坑的地方赋值为1，搜索时遇到1就不走，代码如下：

 

//// Created by hy on 2019/7/13.//#include
     
      using namespace std;typedef long long ll;const int maxn=1005;int zou[maxn][maxn];bool is[maxn][maxn];struct node{    int x;    int y;    int dept;};int x,y;int dic[4][2]={
   {-1,0},{
   0,1},{
   1,0},{
   0,-1}};int bfs(){    queue
      
       qu;    node now,next;    now.x=500;    now.y=500;    now.dept=0;    is[500][500]=1;    qu.push(now);    while(!qu.empty())    {        now=qu.front();        qu.pop();        if(now.x==x+500&&now.y==y+500)            return now.dept;        for(int i=0;i<4;i++)        {            int xx=now.x+dic[i][0];            int yy=now.y+dic[i][1];            if(xx<0||xx>1000||yy<0||yy>1000)                continue;            if(zou[xx][yy]==0&&!is[xx][yy])            {                is[xx][yy]=1;                next.x=xx;                next.y=yy;                next.dept=now.dept+1;                qu.push(next);            }        }    }    return 0;}int main(){    int n;    cin>>x>>y>>n;    memset(is,0,sizeof(is));    memset(zou,0,sizeof(zou));    int p,q;    for(int i=0;i
       
        >p>>q;        zou[p+500][q+500]=1;    }    cout<
        
         <