[SCOI2009] 最长距离

题目描述

windy有一块矩形土地，被分为 NM 块 11 的小格子。有的格子含有障碍物。如果从格子A可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。如果从格子A不可以走到格子B，就没有距离。如果格子X和格子Y有公共边，并且X和Y均不含有障碍物，就可以从X走到Y。如果windy可以移走T块障碍物，求所有格子间的最大距离。保证移走T块障碍物以后，至少有一个格子不含有障碍物。

输入输出格式

输入格式：

第一行包含三个整数，N M T。接下来有N行，每行一个长度为M的字符串，'0'表示空格子，'1'表示该格子含有障碍物。

输出格式：

包含一个浮点数，保留6位小数。

输入输出样例

输入样例#1： 复制

3 3 0

001

001

110

输出样例#1： 复制

1.414214

输入样例#2： 复制

4 3 0

001

001

011

000

输出样例#2： 复制

3.605551

输入样例#3： 复制

3 3 1

001

001

001

Sample Output

输出样例#3： 复制

2.828427

说明

20%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 0 。

40%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 2 。

100%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 30 。

Solution

数据范围30,30，只有900个点，跑900次\(dijkstra\)，复杂度\(n^2logn\)，这里跑的最短路跑的是一个点到另一个点所至少需要走的障碍数，貌似能过，再暴力枚举两个点\(n^2\)判断能不能到达，就这样了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<cmath>

using namespace std;

struct node

{

    int to,next,w;

}a[5010000];

typedef pair<int,int> pr;

priority_queue<pr,vector<pr>,greater<pr> >q;

int len,last[1010010],vis[1010],d[1001][1001],mp[1000][1000],n,m,t;

int ar[]={0,0,1,-1};

int br[]={1,-1,0,0};

void add(int a1,int a2,int a3)

{

    a[++len].to=a2;

    a[len].w=a3;

    a[len].next=last[a1];

    last[a1]=len;

}

int real(int x,int y)

{

    return (x-1)*m+y;

}

void dijkstra(int s)

{

    memset(vis,0,sizeof(vis));

    d[s][s]=0;q.push((pr){0,s});

    while(!q.empty())

    {

        int k=q.top().second;q.pop();

        if(vis[k]) continue;

        vis[k]=1;

        for(int i=last[k];i;i=a[i].next)

        {

            int to=a[i].to;

            if(d[s][to]>d[s][k]+a[i].w)

            {

                d[s][to]=d[s][k]+a[i].w;

                if(!vis[to])

                q.push((pr){d[s][to],to});

            }

        }

    }

}

double dis(int i,int j,int x,int y)

{

    return sqrt((i-x)*(i-x)+(j-y)*(j-y));

}

int main()

{

    char s[50];

    memset(d,0x3f,sizeof(d));

    cin>>n>>m>>t;

    for(int i=1;i<=n;i++)

    {

        scanf("%s",s+1);

        for(int j=1;j<=m;j++)

        if(s[j]=='1') mp[i][j]=1;

    }

    for(int i=1;i<=n;i++)

    for(int j=1;j<=m;j++)

    {

        for(int k=0;k<=3;k++)

        {

            int x=i+ar[k],y=j+br[k];

            if(x==0||y==0||x==n+1||y==m+1) continue;

            add(real(i,j),real(x,y),mp[x][y]);

        }

    }

    double ans=0;

    for(int i=1;i<=n;i++)

    for(int j=1;j<=m;j++)

    dijkstra(real(i,j));

//	cout<<d[8][1]<<endl;

    for(int i=1;i<=n;i++)

    for(int j=1;j<=m;j++)

    for(int x=1;x<=n;x++)

    for(int y=1;y<=m;y++)

    {

        int p1=real(i,j),p2=real(x,y);

        if(mp[i][j]) continue;

        if(d[p1][p2]<=t)

        {

            double pp=dis(i,j,x,y);

            if(ans<pp)

            ans=pp;

        }

    }

    printf("%.6lf",ans);

}

巴特西

[SCOI2009] 最长距离

题目描述

输入输出格式

输入输出样例

说明

Solution

博主蒟蒻，可以随意转载，但必须附上原文链接k-z-j。

最新文章

热门文章