牛客假日团队赛6 F. Mud Puddles

客官°小女子只卖身不卖艺 2023-08-17 15:40 95阅读 0赞

# F. Mud Puddles #

题目链接：[https://ac.nowcoder.com/acm/contest/993/F][https_ac.nowcoder.com_acm_contest_993_F]

**题目：**  
  
农夫约翰早上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<bits/stdc++.h>
    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<node>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<n;i++)
        {
            cin>>p>>q;
            zou[p+500][q+500]=1;
        }
        cout<<bfs()<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11187759.html

[https_ac.nowcoder.com_acm_contest_993_F]: https://ac.nowcoder.com/acm/contest/993/F