2 条题解

  • 0
    @ 2019-01-24 11:45:50
    /*
    
    */
    #define method_1
    #ifdef method_1
    /*
    第一问可以用二分答案
    第二问在二分答案的基础上bfs
    
    为了方便起见,可以在开始位置用bfs预处理出每个点最近的守卫的距离 
    */
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<algorithm>
    #include<map>
    #include<vector>
    #define ll long long
    using namespace std;
    
    int ans1,ans2;
    int head,tail;
    int n,X,Y;
    int x1,y1,x2,y2;
    int mp[1005][1005];
    int x[1000005],y[1000005],step[1000005];
    bool vis[1005][1005];
    int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};
    void pre()
    {
        while(head!=tail)
        {
            int nx=x[head],ny=y[head];head++;
            for(int k=0;k<4;k++)
            {
                int tx=nx+xx[k],ty=ny+yy[k];
                if(tx>=X||ty>=Y||tx<0||ty<0||mp[tx][ty]!=-1)continue;
                mp[tx][ty]=mp[nx][ny]+1;
                x[tail]=tx;y[tail]=ty;tail++;
            }
        }
    }
    int bfs(int val)
    {
        head=0;tail=1;
        if(x1==x2&&y1==y2)return 0;
        memset(vis,0,sizeof(vis));
        vis[x1][y1]=1;x[0]=x1;y[0]=y1;
        while(head!=tail)
        {
            int nx=x[head],ny=y[head],ns=step[head];head++;
            for(int k=0;k<4;k++)
            {
                int tx=nx+xx[k],ty=ny+yy[k];
                if(tx>=X||ty>=Y||tx<0||ty<0||mp[tx][ty]<val||vis[tx][ty])continue;
                vis[tx][ty]=1;
                if(tx==x2&&ty==y2)return ns+1;
                x[tail]=tx;y[tail]=ty;step[tail]=ns+1;tail++;
            }
        }
        return -1;
    }
    int main()
    {
        ios::sync_with_stdio(false);
    //  freopen("赠邻女(寄李亿员外).in","r",stdin);
        memset(mp,-1,sizeof(mp));
        cin>>n>>X>>Y;
        cin>>x1>>y1>>x2>>y2;
        int a,b;
        for(int i=1;i<=n;i++)
        {
            cin>>a>>b;
            mp[a][b]=0;
            x[tail]=a;y[tail]=b;tail++;
        }
        pre();
        int l=0,r=mp[x1][y1];
        while(l<=r)
        {
            int mid=(l+r)>>1;
            int t=bfs(mid);
            if(t==-1)r=mid-1;
            else l=mid+1,ans1=mid,ans2=t;
        }
        cout<<ans1<<" "<<ans2;
        return 0;
    }
    #endif
    #ifdef method_2
    /*
    
    */
    
    #endif
    #ifdef method_3
    /*
    
    */
    
    #endif
    
    
  • -1

    /*

    /
    #define method_1
    #ifdef method_1
    /

    第一问可以用二分答案
    第二问在二分答案的基础上bfs

    为了方便起见,可以在开始位置用bfs预处理出每个点最近的守卫的距离
    */
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<algorithm>
    #include<map>
    #include<vector>
    #define ll long long
    using namespace std;

    int ans1,ans2;
    int head,tail;
    int n,X,Y;
    int x1,y1,x2,y2;
    int mp[1005][1005];
    int x[1000005],y[1000005],step[1000005];
    bool vis[1005][1005];
    int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};
    void pre()
    {
    while(head!=tail)
    {
    int nx=x[head],ny=y[head];head++;
    for(int k=0;k<4;k++)
    {
    int tx=nx+xx[k],ty=ny+yy[k];
    if(tx>=X||ty>=Y||tx<0||ty<0||mp[tx][ty]!=-1)continue;
    mp[tx][ty]=mp[nx][ny]+1;
    x[tail]=tx;y[tail]=ty;tail++;
    }
    }
    }
    int bfs(int val)
    {
    head=0;tail=1;
    if(x1==x2&&y1==y2)return 0;
    memset(vis,0,sizeof(vis));
    vis[x1][y1]=1;x[0]=x1;y[0]=y1;
    while(head!=tail)
    {
    int nx=x[head],ny=y[head],ns=step[head];head++;
    for(int k=0;k<4;k++)
    {
    int tx=nx+xx[k],ty=ny+yy[k];
    if(tx>=X||ty>=Y||tx<0||ty<0||mp[tx][ty]<val||vis[tx][ty])continue;
    vis[tx][ty]=1;
    if(tx==x2&&ty==y2)return ns+1;
    x[tail]=tx;y[tail]=ty;step[tail]=ns+1;tail++;
    }
    }
    return -1;
    }
    int main()
    {
    ios::sync_with_stdio(false);
    // freopen("赠邻女(寄李亿员外).in","r",stdin);
    memset(mp,-1,sizeof(mp));
    cin>>n>>X>>Y;
    cin>>x1>>y1>>x2>>y2;
    int a,b;
    for(int i=1;i<=n;i++)
    {
    cin>>a>>b;
    mp[a][b]=0;
    x[tail]=a;y[tail]=b;tail++;
    }
    pre();
    int l=0,r=mp[x1][y1];
    while(l<=r)
    {
    int mid=(l+r)>>1;
    int t=bfs(mid);
    if(t==-1)r=mid-1;
    else l=mid+1,ans1=mid,ans2=t;
    }
    cout<<ans1<<" "<<ans2;
    return 0;
    }
    #endif
    #ifdef method_2
    /*

    */

    #endif
    #ifdef method_3
    /*

    */

    #endif

  • 1

信息

难度
7
分类
(无)
标签
(无)
递交数
45
已通过
8
通过率
18%
被复制
3
上传者