题解 | Mud Puddles-牛客假日团队赛6F题

F-Mud Puddles_牛客假日团队赛6

https://ac.nowcoder.com/acm/contest/993/F

题目描述

Farmer John is leaving his house promptly at 6 AM for his daily milking of Bessie. However, the previous evening saw a heavy rain, and the fields are quite muddy. FJ starts at the point (0, 0) in the coordinate plane and heads toward Bessie who is located at $(X, Y) (-500 ≤ X ≤ 500; -500 ≤ Y ≤ 500)$ . He can see all $N (1 ≤ N ≤ 10,000)$ puddles of mud, located at points $(A_i, B_i) (-500 ≤ A_i ≤ 500; -500 ≤ B_i ≤ 500)$ on the field. Each puddle occupies only the point it is on.
Having just bought new boots, Farmer John absolutely does not want to dirty them by stepping in a puddle, but he also wants to get to Bessie as quickly as possible. He's already late because he had to count all the puddles. If Farmer John can only travel parallel to the axes and turn at points with integer coordinates, what is the shortest distance he must travel to reach Bessie and keep his boots clean? There will always be a path without mud that Farmer John can take to reach Bessie.

输入描述:

* Line 1: Three space-separate integers: X, Y, and N.

* Lines 2..N+1: Line i+1 contains two space-separated integers: $A_i$ and $Bi_$

输出描述:

* Line 1: The minimum distance that Farmer John has to travel to reach Bessie without stepping in mud.

示例1

输入

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2

输出

11

说明

Bessie is at (1, 2). Farmer John sees 7 mud puddles, located at (0, 2); (-1, 3); (3, 1); (1, 1); (4, 2); (-1, 1) and (2, 2).
The best path for Farmer John is (0, 0); (-1, 0); (-2, 0); (-2, 1); (-2, 2); (-2, 3); (-2, 4); (-1, 4); (0, 4); (0, 3); (1, 3); and (1, 2), finally reaching Bessie.

解答

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

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

#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;
}

来源：_Vampire